题目大意
有两颗不同的树 AAA 和 树 BBB ，每个点都有一个权值，现在两棵树都有 mmm 个节点被标记且被标记的节点编号相同。询问这 mmm 个节点，对于每个被标记节点 xix_ixi ，如果只有这个节点的标记删除，剩下 m−1m-1m−1 个标记节点在树 AAA 中的最近公共祖先的权值是否大于树 BBB 中的最近公共祖先的权值。
题目思路
不难发现，若删****x_ixi 节点的标记，那么要求的 LCALCALCA 是
lca(x1,x2,…,xi−1,xi+1,…,xn−1,xn)=lca(lca(x1,x2,…,xi−1),lca(xi+1,…,xn−1,xn))lca(x_1,x_2,\dots,x_{i-1},x_{i+1},\dots,x_{n-1},x_n)\\ =lca(lca(x_1,x_2,\dots,x_{i-1}),lca(x_{i+1},\dots,x_{n-1},x_n)) lca(x1 ,x2 ,…,xi−1 ,xi+1 ,…,xn−1 ,xn )=lca(lca(x1 ,x2 ,…,xi−1 ),lca(xi+1 ,…,xn−1 ,xn ))
所以我们可以预处理 mmm 个标记节点的前缀 LCALCALCA 和后缀 LCALCALCA ，然后枚举删除标记的节点再求一遍 LCALCALCA ，然后比较两棵树上 LCALCALCA 的权值即可。
时间复杂度 O((n+k)logn)O((n+k)logn)O((n+k)logn)
参考代码
