【UVA11987】Almost Union-Find

题目链接

题目就告诉我们要用并查集了，操作1和3用裸的带权并查集就行了，

操作2相当于将p结点从当前树中删除，再插入到q的树中，直接删除的话比较麻烦，不妨把它的“尸体”留在原来的地方，在q的树中插入一个新的点，维护一个指向编号为p点的指针即可

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;

const int MAXN=2000010;

int n,q,fa[MAXN],size[MAXN],sum[MAXN],m[MAXN],cnt;

inline int read(){
    int x=0; char c=getchar();
    while(c<'0') c=getchar();
    while(c>='0') x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}

inline int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}

int main()
{
    while(scanf("%d%d",&n,&q)!=EOF){
        cnt=n;
        for(int i=1;i<=n;++i)
            fa[i]=i,size[i]=1,sum[i]=i,m[i]=i;
        int op,x,y;
        while(q--){
            op=read();
            if(op==1){
                x=read(),y=read();
                x=m[x]; y=m[y];
                if(find(x)==find(y)) continue;
                if(rand()%2) swap(x,y);
                size[find(y)]+=size[find(x)];
                sum[find(y)]+=sum[find(x)];
                fa[find(x)]=find(y);
            }
            else if(op==2){
                int p=read(),q=read();
                x=m[p]; y=m[q];
                if(find(x)==find(y)) continue;
                --size[find(x)];
                ++size[find(y)];
                sum[find(x)]-=p;
                sum[find(y)]+=p;
                m[p]=++cnt;
                fa[cnt]=find(y);
            }
            else{
                x=read(); x=m[x];
                printf("%d %d\n",size[find(x)],sum[find(x)]);
            }
        }
    }
    return 0;
}