有n棵树，要求支持4种操作：把两棵树所在森林合并；把一颗树从森林中分离出来；问某棵树所属森林的大小；问两棵树是否在同一个森林中。

如果没有查询树的大小（操作3）那肯定一个并查集解决。

加上这个操作3就麻烦了。

我们怎么维护一个森林的大小？

暴力必不可能。。。

每次合并和删除的时候直接改根节点也会出问题，因为不是所有节点都路径压缩过。

所以我们可以在把一个节点独立的时候直接舍去这个节点，新建一个新的节点来代替原来的节点。

然后根节点存的森林大小直接-1即可，因为之后的事和废弃节点无瓜。

这样就可以了。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 200010
using namespace std;
int n,m,fa[MAXN],size[MAXN],id[MAXN];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void uniun(int x,int y){
    x=find(id[x]);y=find(id[y]);
    if(x!=y){
        fa[x]=y;
        size[y]+=size[x];
    }
}
bool check(int x,int y){x=find(id[x]);y=find(id[y]);return x==y;}
void remove(int x){size[find(id[x])]--;id[x]=++n;}
void work(){
    int f,x,y;
    while(m--){
        f=read();x=read();
        if(f==1){
            y=read();
            uniun(x,y);
        }
        else if(f==2){
            remove(x);
        }
        else if(f==3){
            printf("%d\n",size[find(id[x])]);
        }
        else if(f==4){
            y=read();
            printf(check(x,y)?"YES\n":"NO\n");
        }
    }
}
void init(){
    memset(fa,0,sizeof(fa));
    memset(size,0,sizeof(size));
    memset(id,0,sizeof(id));
    n=read();m=read();
    for(int i=1;i<=n+m;i++){
        id[i]=fa[i]=i;
        size[i]=1;
    }
}
int main(){
    int t=read();
    for(int cases=1;cases<=t;cases++){
        printf("Case #%d:\n",cases);
        init();
        work();
    }
    return 0;
}