ACM-ICPC 2019 南昌区域赛 A. 9102 可撤销并查集

题目链接：https://nanti.jisuanke.com/t/42576
题目大意：

思路：可撤销并查集
我们把操作建立成一个时间树。然后就可以在树上可撤销并查集。
对于操作3：我们新开个点作为镜像代替a，连向b。和题目uva11987类似。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct node{
    int id;
    int form, to, x, y;
}sk[2000005];
int top=0;

struct Dsu{

    //p元素所在集合全部元素的和。
    //p元素集合的元素个数
    int a[2000005];
    int f[2000005], sum[2000005], num[2000005];
    int id[2000005];//是否删除-1 镜像节点的id
    int tot;//新节点
    void init(int n){
        top=0;
        for(int i=1; i<=n; i++){
            f[i]=-1; sum[i]=a[i];
            num[i]=1; id[i]=0;
        }
        tot=n;
    }

    int fd(int x){
        if(f[x]==-1) return x;
        return fd(f[x]);
    }

    //删除x节点
    void Delete(int x){
        if(id[x]==-1) return ;

        int fx=id[x]?fd(id[x]):fd(x);

        sk[++top]=node{3, x, id[x], fx};
        id[x]=-1;
        sum[fx]--, num[fx]--;

    }

    //连接x, y集合
    int link(int x, int y){
        if(id[x]==-1||id[y]==-1) return 0;
        int fx=id[x]?fd(id[x]):fd(x);
        int fy=id[y]?fd(id[y]):fd(y);

        if(fx==fy) return 0;
        if(sum[fx]>=sum[fy]){
            sk[++top]=node{1, fy, fx};

            sum[fx]+=sum[fy];
            num[fx]+=num[fy];
            f[fy]=fx;
        }
        else{
            sk[++top]=node{1, fx, fy};

            sum[fy]+=sum[fx];
            num[fy]+=num[fx];;
            f[fx]=fy;
        }
        return 1;
    }


    //把x节点移到y在的集合
    int movex(int x, int y){
        if(id[x]==-1||id[y]==-1) return 0;

        int fx=id[x]?fd(id[x]):fd(x);
        int fy=id[y]?fd(id[y]):fd(y);
        if(fx==fy) return 0;

        sk[++top]=node{2, fx, fy, x, id[x]};

        id[x]=++tot;
        f[id[x]]=fy;

        sum[fx]-=a[x]; num[fx]--;
        sum[fy]+=a[x]; num[fy]++;


        return 1;
    }

    //回退到sk。size()==pos的时间点
    void revoke(int pos){
        while(top>pos){
            if(sk[top].id==1){
                node t=sk[top]; top--;

                f[t.form]=-1;
                sum[t.to]-=sum[t.form];
                num[t.to]-=num[t.form];
            }
            else if(sk[top].id==2){
                node t=sk[top]; top--;

                f[tot]=0;
                id[t.x]=t.y; --tot;
                sum[t.form]+=a[t.x]; num[t.form]++;
                sum[t.to]-=a[t.x]; num[t.to]--;
            }
            else{
                node t=sk[top]; top--;

                id[t.form]=t.to;
                sum[t.x]++, num[t.x]++;
            }
        }
    }
}T;

struct Q{
    int op;
    int x, y;
}e[1000005];

vector<int> G[1000005];
int ans[1000005];
void DFS(int u){

    if(e[u].op==1){
        if(T.id[e[u].x]==-1||T.id[e[u].y]==-1){}
        else{
            T.link(e[u].x, e[u].y);
        }
    }
    else if(e[u].op==2){
        T.Delete(e[u].x);
    }
    else if(e[u].op==3){
        T.movex(e[u].x, e[u].y);
    }
    else if(e[u].op==4){
        if(T.id[e[u].x]==-1||T.id[e[u].y]==-1){
            ans[u]=-2;
        }
        else{
            int x=e[u].x, y=e[u].y;
            int fx=T.id[x]?T.fd(T.id[x]):T.fd(x);
            int fy=T.id[y]?T.fd(T.id[y]):T.fd(y);
            if(fx==fy){
                ans[u]=-1;
            }
            else{
                ans[u]=-2;
            }
        }
    }
    else if(e[u].op==5){
        if(T.id[e[u].x]==-1){
            ans[u]=0;
        }
        else{
            int x=T.id[e[u].x]?T.fd(T.id[e[u].x]):T.fd(e[u].x);
            ans[u]=T.sum[x];
        }
    }
    int pos=top;
    for(auto x: G[u]){

        DFS(x);
        T.revoke(pos);//回退
    }
}

int main() {

    int n, q; scanf("%d%d", &n ,&q);
    for(int i=1; i<=n; i++){
        T.a[i]=1;
    }
    for(int i=1; i<=q; i++){
        ans[i]=-3;
        G[i].clear();
    }
    T.init(n);
    int op, k, x, y;
    for(int i=1; i<=q; i++){
        scanf("%d%d%d", &op, &k, &x);
        if(op!=2&&op!=5){
            scanf("%d", &y);
        }
        G[k].push_back(i);//时间树
        e[i]={op, x, y};
    }
    DFS(0);
    for(int i=1; i<=q; i++){
        if(ans[i]==-1){
            printf("Yes\n");
        }
        if(ans[i]==-2){
            printf("No\n");
        }
        if(ans[i]>=0){
            printf("%d\n", ans[i]);
        }
    }

    return 0;
}