Problem - E - Codeforces
题意:
思路:
注意到题目的性质:满足条件的路径个数是极少的,因为每个点离路径的距离<=1
先考虑一条链,那么直接就选最深那个点作为端点即可
为什么,因为我们需要遍历所有点的父亲
推广到树,也是要遍历所有点的父亲
为什么要加枚举的tag,因为可以发现满足条件的链的状态数很少,可以把这个作为切入点
文章来源:https://www.toymoban.com/news/detail-621528.html
Code:文章来源地址https://www.toymoban.com/news/detail-621528.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模板网!