CF-629-E. Tree Queries E. 树形查询 · znzryb
## 思路讲解
先把所有点替换为其父节点，然后使用
$LCA（a1,a2）=a1(a1为深度较浅点)\Rightarrow a1在1->a2的路径上$这个结论。
```cpp
for(int i=1;i<=M;++i){
sort(que[i].begin(),que[i].end(),cmp);
for(int j=0;j<que[i].size();++j){
que[i][j]=Fa[que[i][j]];
}
ll din=in[que[i].back()],dout=out[que[i].back()];
bool isB=false;
for(int j=(int)que[i].size()-2;j>=0;--j){
ll node=que[i][j];
if(in[node]<=din && out[node]>=dout){ // node是不是最深点的父节点？
}else{
cout<<"NO\n";isB=true;
break;
}
}
if(!isB)cout<<"YES\n";
}
```
## AC代码
[https://codeforces.com/group/vXvHT09g9Y/contest/1328/submission/327207452](https://codeforces.com/group/vXvHT09g9Y/contest/1328/submission/327207452)
::: 源代码
```cpp
// Problem: E. Tree Queries
// Contest: Codeforces - Codeforces Round 629 (Div. 3)
// URL: https://codeforces.com/group/vXvHT09g9Y/contest/1328/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":"<<x<<"\n";
using namespace std;
using ll = long long;
constexpr ll MAXN=(ll)2e5+10;constexpr ll INF=(ll)1e17+9;
constexpr ll mod=(ll)1e9+7;constexpr double eps=1e-8;const double pi=acos(-1.0);
/*
*/
vector<ll> g[MAXN]; // 记得要清空
vector<ll> que[MAXN];
ll deep[MAXN];
bitset<MAXN> vis;
ll Fa[MAXN],out[MAXN],in[MAXN];
bool cmp(const ll &a,const ll &b){
return deep[a]<deep[b];
}
inline void solve(){
ll N,M;
cin>>N>>M;
for(int i=1;i<=N-1;++i){
ll u,v;cin>>u>>v;
g[u].push_back(v);g[v].push_back(u);
}
for(int i=1;i<=M;++i){
ll k;
cin>>k;
for(int j=1;j<=k;++j){
ll v;cin>>v;
que[i].push_back(v);
}
}
ll toti=0,toto=0;
auto dfs=[&](auto &&self,ll u,ll dep,ll pa)->void{ // 在外面调用的时候dfs(dfs,u)
vis[u]=true,deep[u]=dep,Fa[u]=pa,in[u]=++toti;
for(int i=0;i<g[u].size();++i){
ll v=g[u][i];
if(vis[v]) continue;
self(self,v,dep+1,u);
}
out[u]=++toto;
};
dfs(dfs,1,0,1);
for(int i=1;i<=M;++i){
sort(que[i].begin(),que[i].end(),cmp);
for(int j=0;j<que[i].size();++j){
que[i][j]=Fa[que[i][j]];
}
ll din=in[que[i].back()],dout=out[que[i].back()];
bool isB=false;
for(int j=(int)que[i].size()-2;j>=0;--j){
ll node=que[i][j];
if(in[node]<=din && out[node]>=dout){
}else{
cout<<"NO\n";isB=true;
break;
}
}
if(!isB)cout<<"YES\n";
}
// #ifdef LOCAL
// for(int i=1;i<=N;++i){
// cerr<<deep[i]<<" ";
// }
// cerr<<"\n";
// #endif
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// ll lT;
// cin>>lT;
// while(lT--){
// solve();
// }
solve();
return 0;
}
/*
AC
https://codeforces.com/group/vXvHT09g9Y/contest/1328/submission/327207452
*/
```
:::
## 心路历程（WA，TLE，MLE……）