边带权的并查集

使用d[a]额外记录从a到根节点的距离，se记录某个集合的大小

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 30005;
int t;
int f[N], d[N], se[N];

int search(int a)
{
    if(a == f[a]) return a;
    int father = search(f[a]);
    d[a] += d[f[a]];
    return f[a] = father;
}

void merge(int a, int b)
{
    a = search(a);
    b = search(b);
    f[a] = b;
    //重复合并会使d和se偏大
    d[a] = se[b];
    se[b] += se[a];
}

int main()
{
    cin >> t;
    for(int i = 1; i <= N; i++) f[i] = i, se[i] = 1;
    while(t--)
    {
        char x;
        int a, b;
        cin >> x >> a >> b;
        if(x == 'M')
        {
            if(search(a) != search(b))
            merge(a, b);
        }
        else if(x == 'C')
        {
            int res = 0;
            if(search(a) != search(b)) res = -1;
            else res = abs(d[a] - d[b]);

            if(res > 0) res--;
            cout << res << endl;
        }

    }

    return 0;
}