【AGC014E】Blue and Red Tree

比眉伴天荒 2023-10-11 06:30 20阅读 0赞

[题目][Link 1]

正着考虑把边割断感觉非常难以考虑，于是考虑一下将整个过程倒过来，也就是把红边树变成蓝边树

不难发现最后一步我们割断的边肯定是两棵树上都有的边，毕竟最后一步的时候原树只剩下了一条边

如果两棵树没有公共边，那么直接输出\\(\\text\{NO\}\\)即可

再来考虑一下\\(n-2\\)步是怎么操作的

不难发现我们可能是继续操作一条公共边，把这条蓝边变成红边；或者是选择两个**不能通过蓝边相连的点但是两点的路径上只有一条边不是蓝边的点**，之后把这条蓝边给连上

这个不能通过蓝边相连但是两点路径上只有一条红边的条边看起来非常难以表示，但是我们考虑把形成的蓝边联通块缩在一起，发现这个条件就变成了这两个点之间有一条红边相连。当然这条红边也必须得是目标红边树里的边。

于是现在做法很明确了，就是找到两棵树的公共边，将公共边缩成一个点。继续进行这个过程，知道最后整棵树能缩成一个点，答案就是\\(\\text\{YES\}\\)；否则就是\\(\\text\{NO\}\\)

我们用并查集维护一下联通块的情况，启发式合并边集即可

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    #define mp std::make_pair
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    #pragma GCC optimize(3)
    #pragma GCC optimize("-fcse-skip-blocks")
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=1e5+5;
    std::set<int> e[2][maxn];
    std::set<int>::iterator it;
    typedef std::pair<int,int> pii;
    std::map<pii,int> ma[2];
    int n,tot,fa[maxn];
    pii q[maxn];
    inline int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
    inline pii get(int x,int y) {if(x<y) std::swap(x,y);return mp(x,y);}
    inline void merge(int x,int y) {
        x=find(x),y=find(y);
        if(x==y) return;
        if(e[0][x].size()+e[1][x].size()<e[0][y].size()+e[1][y].size()) 
            std::swap(x,y);
        e[0][y].erase(x);e[0][x].erase(y);
        for(it=e[0][y].begin();it!=e[0][y].end();++it) {
            int now=(*it);
            ma[0][get(now,y)]=0;ma[0][get(x,now)]=1;
            if(ma[1][get(x,now)]) q[++tot]=mp(x,now);
            e[0][x].insert(now);e[0][now].erase(y);e[0][now].insert(x);
        }
        e[1][y].erase(x);e[1][x].erase(y);
        for(it=e[1][y].begin();it!=e[1][y].end();++it) {
            int now=(*it);
            ma[1][get(y,now)]=0;ma[1][get(x,now)]=1;
            if(ma[0][get(x,now)]) q[++tot]=mp(x,now);
            e[1][x].insert(now);e[1][now].erase(y);e[1][now].insert(x);
        }
        fa[y]=x;
    }
    int main() {
        n=read();
        for(re int i=1;i<=n;i++) fa[i]=i;
        for(re int x,y,i=1;i<n;i++) {
            x=read(),y=read();
            e[0][x].insert(y),e[0][y].insert(x);
            if(x<y) std::swap(x,y);
            ma[0][mp(x,y)]++;
        }
        for(re int x,y,i=1;i<n;i++) {
            x=read(),y=read();
            e[1][x].insert(y),e[1][y].insert(x);
            if(x<y) std::swap(x,y);
            if(ma[0][mp(x,y)]) q[++tot]=mp(x,y);
            ma[1][mp(x,y)]++;
        }
        for(re int i=1;i<=tot;i++) merge(q[i].first,q[i].second);
        for(re int i=1;i<=n;i++) fa[i]=find(i);
        for(re int i=2;i<=n;i++) if(fa[1]!=fa[i]) {puts("NO");return 0;}
        puts("YES");return 0;
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11557271.html

[Link 1]: https://www.luogu.org/problem/AT2377