2022牛客多校（三）

2022牛客多校（三）

一、比赛小结

比赛链接："蔚来杯"2022牛客暑期多校训练营3

这场一堆神仙知识， 听都没听过 ，回头再补

二、题目分析及解法（基础题） A、Ancestor

题目链接：A-Ancestor_

题意：

给出两棵编号 1-n 的树A、B，A B树上每个节点均有一个权值，给出k个关键点的编号 x 1 , … , x n x_1,…,x_n x1​,…,xn​，问有多少种方案使得去掉恰好一个关键点使得剩余关键点在树A上LCA的权值大于树B上LCA的权值。

题解：

预处理出关键点序列的在树A B上的前缀LCA和后缀LCA，枚举去掉的关键节点并使用前后缀LCA算出剩余节点的LCA比较权值即可。

代码：

#include 
#include 
// #define int long long 会RE ？？？
using namespace std;
const int maxn = 2e5 + 5;
int n, k;
int pre1[maxn], deep1[maxn], num1[maxn], son1[maxn];  // 第一次dfs的变量
int dfn1[maxn], top1[maxn], rk1[maxn], id1;  // 第二次dfs的时候用到的变量
int val1[maxn], dfnval1[maxn];               // 建树时用dfn序下的val
int pre2[maxn], deep2[maxn], num2[maxn], son2[maxn];  // 第一次dfs的变量
int dfn2[maxn], top2[maxn], rk2[maxn], id2;  // 第二次dfs的时候用到的变量
int val2[maxn], dfnval2[maxn];               // 建树时用dfn序下的val
int head2[maxn], cnt2;
int x[maxn], a[maxn], b[maxn];
int anc1, anc2;

int preanc1[maxn], preanc2[maxn];
int last1[maxn], last2[maxn];
struct e {
  int to, next;
} edge1[maxn