【树链】CF1702 G

我不是女神ヾ 2024-03-17 21:17 87阅读 0赞

[Problem - G2 - Codeforces][]

题意：

![2f767a716e2043b3b148c05fc5bef7a1.png][]

思路：

首先，一条树链可以被分为两部分：左半部分和右半部分

我们可以把所有可能是链上的点排序，把深度最大的点默认成起点st，接下来去找终点ed

ed在**和st不同的链上** 且 **深度最大**

即lca(V\[i\],st)!=V\[i\]且深度最大

那么可以把除了这条链的点排序，取深度最大的点作为ed即可

记G=lca(st,ed)

然后去check所有点是否在链上

如果点在链上，那么lca(V\[i\],st\])=G||lca(V\[i\],ed)=G

如果两个都不满足，那么该点一定不是链上的点

还有一种情况是：G可能分裂成多条链，即V2\[i\]中的点可能和ed的lca不为V2\[i\]，去除这种情况即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int N,Q,u,v,x,K;
    int tot=0;
    int head[mxn];
    int dep[mxn],F[mxn][33];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void dfs(int u,int fa){
    	dep[u]=dep[fa]+1;
    	F[u][0]=fa;
    	for(int j=1;j<=20;j++) F[u][j]=F[F[u][j-1]][j-1];
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs(edge[i].to,u);
    	}
    }
    bool cmp(int x,int y){
    	return dep[x]<dep[y];
    }
    int lca(int u,int v){
    	if(dep[u]<dep[v]) swap(u,v);
    	for(int j=30;j>=0;j--){
    		if(dep[F[u][j]]>=dep[v]){
    			u=F[u][j];
    		}
    	}
    	if(u==v) return u;
    	for(int j=30;j>=0;j--){
    		if(F[u][j]!=F[v][j]){
    			u=F[u][j];
    			v=F[v][j];
    		}
    	}
    	return F[u][0];
    }
    void solve(){
    	cin>>N;
    	G_init();
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    	}
    	dfs(1,0);
    	cin>>Q;
    	while(Q--){
    		vector<int> V,V2;
    		cin>>K;
    		for(int i=1;i<=K;i++){
    			cin>>x;
    			V.push_back(x);
    		}
    		sort(V.begin(),V.end(),cmp);
    		int st=V.back();
    		for(int i=0;i<V.size()-1;i++){
    			if(lca(st,V[i])!=V[i]) V2.push_back(V[i]);
    		}
    		if(V2.empty()){
    			cout<<"YES"<<'\n';
    			continue;
    		}
    		sort(V2.begin(),V2.end(),cmp);
    		int ed=V2.back();
    		int G=lca(st,ed);
    		int ok=1;
    		for(int i=0;i<V2.size()-1;i++){
    			if(lca(V2[i],ed)!=V2[i]) ok=0;
    		}
    		for(int i=0;i<V.size();i++){
    			if(lca(V[i],st)!=G&&lca(V[i],ed)!=G) ok=0;
    		}
    		if(ok) cout<<"YES"<<'\n';
    		else cout<<"NO"<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - G2 - Codeforces]: https://codeforces.com/contest/1702/problem/G2
[2f767a716e2043b3b148c05fc5bef7a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/54e43111b79443c19b89b839261851c8.png