CF1827E Bus Routes

发布时间 2023-06-23 21:47:19作者: DPD

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;
}
View Code