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

今天我們來看看CF1328E

題目連結

題目

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

前言

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

@copyright petjelinux 版權所有

觀看更多正版原始文章請至petjelinux的blog

想法

可以觀察到，題目的敘述表示，對於一個節點\(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

E. Tree Queries 解析(思維、LCA)的相关教程结束。