官方题解

题目大意

有两颗不同的树 $A$ 和 树 $B$ ，每个点都有一个权值，现在两棵树都有 $m$ 个节点被标记且被标记的节点编号相同。询问这 $m$ 个节点，对于每个被标记节点 $x_i$ ，如果只有这个节点的标记删除，剩下 $m-1$ 个标记节点在树 $A$ 中的最近公共祖先的权值是否大于树 $B$ 中的最近公共祖先的权值。

题目思路

不难发现，若删除 $x_i$ 节点的标记，那么要求的 $LCA$ 是

$$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))$$

所以我们可以预处理 $m$ 个标记节点的前缀 $LCA$ 和后缀 $LCA$ ，然后枚举删除标记的节点再求一遍 $LCA$ ，然后比较两棵树上 $LCA$ 的权值即可。

时间复杂度 $O((n+k)logn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e18+10;
const int N = 200010;

vector<int>v[2][N];
int q[N],a[N],b[N];
int pre[2][N],suf[2][N];
int fa[2][N],dep[2][N],sz[2][N],son[2][N],top[2][N];

void dfs1(int id,int u){
	sz[id][u]=1;
	dep[id][u]=dep[id][fa[id][u]]+1;

	for(auto x:v[id][u]){
		if(x==fa[id][u]) continue;
		fa[id][x]=u;
		dfs1(id,x);
		sz[id][u]+=sz[id][x];
		if(sz[id][x]>sz[id][son[id][u]]) son[id][u]=x;
	}
}
void dfs2(int id,int u,int h){
	top[id][u]=h;
	if(son[id][u]) dfs2(id,son[id][u],h);
	for(auto x:v[id][u]){
		if(x==fa[id][u] || x==son[id][u]) continue;
		dfs2(id,x,x);
	}
}

int lca(int id,int x,int y){
	while(top[id][x]!=top[id][y]){
		if(dep[id][top[id][x]]>dep[id][top[id][y]]) x=fa[id][top[id][x]];
		else y=fa[id][top[id][y]];
	}
	return dep[id][x]<dep[id][y] ? x : y;
}

int main(){
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=2;i<=n;i++){
        int x;cin>>x;
		v[0][i].push_back(x);
		v[0][x].push_back(i);
	}
	dfs1(0,1);
	dfs2(0,1,1);
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=2;i<=n;i++){
        int x;cin>>x;
		v[1][i].push_back(x);
		v[1][x].push_back(i);
	}
    for(int i=1;i<=k;i++) cin>>q[i];
	dfs1(1,1);
	dfs2(1,1,1);

	pre[0][1]=pre[1][1]=q[1];
	for(int i=2;i<=k;i++){
		pre[0][i]=lca(0,pre[0][i-1],q[i]);
		pre[1][i]=lca(1,pre[1][i-1],q[i]);
	}
	suf[0][k]=suf[1][k]=q[k];
	for(int i=k-1;i>=1;i--){
		suf[0][i]=lca(0,suf[0][i+1],q[i]);
		suf[1][i]=lca(1,suf[1][i+1],q[i]);
	}

	int res=0;
	for(int i=1;i<=k;i++){
		int la,lb;
		if(i==1){
			la=suf[0][i+1];
			lb=suf[1][i+1];
		}
		else if(i==k){
			la=pre[0][i-1];
			lb=pre[1][i-1];
		}
		else{
			la=lca(0,pre[0][i-1],suf[0][i+1]);
			lb=lca(1,pre[1][i-1],suf[1][i+1]);
		}
		
		if(a[la]>b[lb]) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}