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

Problem - E - Codeforces

题意：

思路：

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

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

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

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

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

Code：

#include <bits/stdc++.h>#define int long longusing 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;
}