CF1827E Bus Routes
很有思维含量的一道题。
任意钦定一个根 $rt$,对于每个节点,如果它不能到达,那么他的子树内所有点一定也不能到达,因此,我们只用考虑每一个叶子节点的情况。对每个叶子节点 $u$,设 $low_{u}$ 表示他能通过一条路线到达的最浅的祖先。对于任意两叶子节点,如果他们的low不是祖先关系,那么他们就无法相互到达。直接输出即可。否则,我们以最深的low为跟,重复上面的过程,看他们的low是不是v,如果不是则输出。(可能有点抽象,具体看代码)
#include<bits/stdc++.h> using namespace std; const int N=6e5+555; int Q,n,m,dep[N],low[N],f[N][21]; vector<int> g[N],r[N]; inline void dfs(int u,int fath){ f[u][0] = fath; for(int i=1;i<=20;i++) f[u][i] = f[f[u][i - 1]][i - 1]; for(int v:g[u]){ if(v==fath) continue; dep[v]=dep[u]+1; dfs(v,u); } } inline int LCA(int u, int v){ if(dep[u] < dep[v]) swap(u, v); for(int i=20;i>=0;i--) if(dep[f[u][i]] >= dep[v]) u = f[u][i]; if(v == u) return u; for(int i=20;i>=0;i--) if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i]; return f[u][0]; } inline bool cmp(int a, int b){ return dep[low[a]] < dep[low[b]]; } inline void work(){ for(int i=1;i<=n;i++){ g[i].clear();r[i].clear(); } scanf("%d%d", &n, &m); for(int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } for(int i=1,v,u;i<=m;i++){ scanf("%d%d",&u,&v); r[u].push_back(v); r[v].push_back(u); } dfs(1,1); vector<int> zx; for(int u=1;u<=n;u++){ low[u]=u; if(g[u].size()==1){ zx.push_back(u); for(int v:r[u]){ int uu=LCA(u,v); if(dep[uu]<dep[low[u]]){ low[u]=uu; } } } } sort(zx.begin(),zx.end(),cmp); for(int i=0;i<zx.size()-1;i++){ if(LCA(low[zx[i]],low[zx[i+1]])!=low[zx[i]]){ printf("NO\n%d %d\n", zx[i], zx[i + 1]); return; } } int rt=low[zx.back()]; dep[rt]=0; dfs(rt,rt); for(int u:zx){ int z=u; for(int v:r[u]){ int uu=LCA(u,v); if(dep[uu]<dep[z]) z=uu; } if(rt!=z){ printf("NO\n%d %d\n", u, zx.back()); return ; } } printf("YES\n"); return; } int main(){ cin>>Q; while(Q--){ work(); } return 0; }