带权并查集+最小生成树

https://www.luogu.org/problem/P1196

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int fa[maxn],sum[maxn],son[maxn];
struct dd {
    int faa,val;
    dd(int xx=0,int yy=0):faa(xx),val(yy) {
    }
};
int getf(int x) {
    if(fa[x]==x)return x;
    else {
        int fa1=getf(fa[x]);
        sum[x]+=sum[fa[x]];
        return fa[x]=fa1;//传回去的不能直接用
    }
}
int get_son(int x) {
    if(son[x]==x)return x;
    else {
        return son[x]=get_son(son[x]);
    }
}
int size[maxn];//重点
int main() {
    int t;
    cin>>t;
    for(int i=1; i<=30000+10; i++)fa[i]=i,sum[i]=0,son[i]=i,size[i]=1;
//初始化一定要为0
    // a 是自己开一个a所在的是加到b下面
    for(int i=1; i<=t; i++) {
        char d;
        cin>>d;
        if(d=='C') {
            int x,y;
            cin>>x>>y;
            int r=getf(x);
            int k=getf(y);
            if(r!=k) {
                cout<<"-1"<<endl;
            } else
                cout<<abs(sum[x]-sum[y])-1<<endl;
        } else {
            int x,y;
            cin>>x>>y;
            int r=getf(x),r1=getf(y),son1=get_son(y);
            son[son1]=r;
            fa[r]=r1;//直接转为最上面的，要不然，你会炸的很惨。因为会多算
            sum[r]=size[r1];//它上面有多少？
            size[r1]+=size[r];
        }
    }

    return 0;
}

自己构造的一组数据，却成了环。。。。。。我吐，写出来警示后人

1000
M 1 2
M 2 3
C 1 3
M 4 5
M 5 6
M 6 1
C 2 4

M 3 4
C 2 4

C 4 3

C 2 5

C 4 3

C 4 3

C 4 3

C 4 3

C 4 3