Codeforce 1328 E. Tree Queries 解析(思維、LCA)

今天我們來看看CF1328E
題目連結

題目
給你一棵樹，並且給你$m\le2e5$個詢問(包含$k$個點)，求能不能找到一個從點$1$開始的路徑，使得這$k$個點離這個路徑的距離$\le1$

前言

久違的沒看解答寫的題目，故寫題解

想法

可以觀察到，題目的敘述表示，對於一個節點$v$，他的子節點是可以同時出現的。因此我們只需要關注$k$個點的每個點的父節點能不能形成一個路徑，而要判斷一個點集能不能成為一條路徑，我們只需要先把點集以點的深度排序，接著從深度低的點兩個兩個看，對於點對$(u,v)$，如果$lca(u,v)=u$($u$是深度低的點)，就代表我們能夠從$u$連到$v$。

程式碼:

const int _n=2e5+10,MAXB=19;  
int n,m,u,v,k,a,b,dep[_n],fa[_n][MAXB];  
VI G[_n];  
void dfs(int v,int faa,int d){  
  dep[v]=d;fa[v][0]=faa;  
  rep(i,0,SZ(G[v]))if(faa!=G[v][i])dfs(G[v][i],v,d+1);  
}  
void bfa(){  
  rep(j,1,MAXB)rep(i,1,n+1)if(~fa[i][j-1])  
    fa[i][j]=fa[fa[i][j-1]][j-1];  
}  
int lca(int a,int b){  
  if(dep[a]<dep[b])swap(a,b);  
  per(j,0,MAXB)if(~fa[a][j] and dep[fa[a][j]]>=dep[b])a=fa[a][j];  
  if(a==b)return a;  
  per(j,0,MAXB)if(~fa[a][j] and fa[a][j]!=fa[b][j])a=fa[a][j],b=fa[b][j];  
  return fa[a][0];  
}  
bool cmp(const int& a,const int& b){return dep[a]<dep[b];}  
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);  
  cin>>n>>m;rep(i,0,n-1){cin>>u>>v;G[u].pb(v),G[v].pb(u);}  
  dfs(1,-1,0);rep(i,1,n+1)rep(j,1,MAXB)fa[i][j]=-1; bfa();  
  while(m--){  
    cin>>k;VI ks;rep(i,0,k){cin>>v;ks.pb(v);}  
    rep(i,0,k)ks[i]=(fa[ks[i]][0]==-1?1:fa[ks[i]][0]);  
    sort(all(ks),cmp);  
    rep(i,1,k)if(lca(ks[i-1],ks[i])!=ks[i-1]){cout<<"NO\n";goto A;}  
    cout<<"YES\n";  
    A:;  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission