【*1900 图论+枚举思想】CF1328 E

约定不等于承诺〃 2024-03-22 21:14 84阅读 0赞

[Problem - E - Codeforces][]

题意：

![5f242b3e379b424cb713c6418d07f247.png][]

![5e58cd37404e493d9f8003a3c85c9281.png][]

![3c0775d133d343eb8fe225ee51afd9aa.png][]

![d1186513f96f4cb8bf627ccb7079e676.png][]

思路：

注意到题目的性质：满足条件的路径个数是极少的，因为每个点离路径的距离**<=1**

先考虑一条链，那么直接就选最深那个点作为端点即可

为什么，因为我们需要遍历所有点的父亲

推广到树，也是要遍历所有点的父亲

为什么要加枚举的tag，因为可以发现满足条件的链的状态数很少，可以把这个作为切入点

![f626f7aa0e9246c7895b51d358b2628e.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mod=1e9+7;
    
    vector<int> G[mxn];
    
    int N,M,K,u,v,x;
    int idx=0;
    int dep[mxn],In[mxn],sz[mxn],F[mxn];
    
    void dfs(int u,int fa){
    	sz[u]=1;
    	F[u]=fa;
    	dep[u]=dep[fa]+1;
    	In[u]=++idx;
    	for(auto v:G[u]){
    		if(v==fa) continue;
    		dfs(v,u);
    		sz[u]+=sz[v];
    	}
    }
    bool cmp(int x,int y){
    	return dep[x]<dep[y];
    }
    bool check(int u,int v){
    	return In[v]>=In[u]&&In[v]<=In[u]+sz[u]-1;
    }
    void init(){
    	for(int i=0;i<=N;i++){
    		dep[i]=In[i]=sz[i]=F[i]=0;
    		G[i].clear();
    	}
    }
    void solve(){
    	cin>>N>>M;
    	init();
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		G[u].push_back(v);
    		G[v].push_back(u);
    	}
    	dfs(1,0);
    	F[1]=1;
    	while(M--){
    		cin>>K;
    		vector<int> V;
    		for(int i=1;i<=K;i++){
    			cin>>x;
    			V.push_back(F[x]);
    		}
    		//for(int i=0;i<V.size();i++) cout<<V[i]<<" \n"[i==V.size()-1];
    		sort(V.begin(),V.end(),cmp);
    		int ok=1;
    		for(int i=1;i<V.size();i++){
    			if(!check(V[i-1],V[i])){
    				ok=0;
    				break;
    			} 
    		}
    		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 - E - Codeforces]: https://codeforces.com/contest/1328/problem/E
[5f242b3e379b424cb713c6418d07f247.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/62802125b95247be9b29ecc3056acf8f.png
[5e58cd37404e493d9f8003a3c85c9281.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/fcff5d6276c34b278fcc3a7e8ea46a38.png
[3c0775d133d343eb8fe225ee51afd9aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/433688ef116c47be82f3e3a60d19bbd3.png
[d1186513f96f4cb8bf627ccb7079e676.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/85d6654f072e4d33ac184ba00acbcea5.png
[f626f7aa0e9246c7895b51d358b2628e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8087c74f015a4353a18f9003f46912a5.png