【*1900 图论】CF1328 E-Toy模板网

这篇具有很好参考价值的文章主要介绍了【*1900 图论】CF1328 E。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Problem - E - Codeforces

题意：

【*1900 图论】CF1328 E,图论,图论

思路：

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

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

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

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

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

【*1900 图论】CF1328 E,图论,图论

Code：文章来源地址https://www.toymoban.com/news/detail-609284.html

#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;
}

到了这里，关于【*1900 图论】CF1328 E的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！