带权并查集_牛客博客

参考资料: https://blog.csdn.net/yjr3426619/article/details/82315133
https://www.cnblogs.com/yifusuyi/p/9404672.html
P196 银河英雄传说
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long ll;
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
#define vec(i) for (int i = head[x]; i; i = nxt[i])
#define clr(a,b)  memset((a),b,sizeof(a))
using namespace std;
const int N = 1e5 + 20;
const int M = 505;
inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9')   { if(ch == '-') w = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar(); }
    return s * w;
}
int t, fa[N], siz[N], sum[N];
//siz[i]：i所在的链的规模 
//sum[i]：i到其所在根节点的距离 
int find(int x) {
    if(x == fa[x]) return x;
    else {
        int t = fa[x];    //先记录下fa 
        fa[x] = find(fa[x]);   // 当返回时，fa[x]已经改变，即当此句执行完后 fa[x] != t 
        siz[x] = siz[t]; 
        sum[x] += sum[t];   // 合并父亲的权值 
    }
    return fa[x];
}
//带权并查集实际上就类似于前缀和，通过已知的两个相对信息求出一个绝对信息
int main() {
    t = read();
    rep(i, 1, 30000) fa[i] = i, siz[i] = 1;
    while(t --) {
        char c = getchar(); while(c != 'M' && c != 'C') c = getchar();
        if(c == 'M') {
            int x = read(), y = read();
            int a = find(x), b = find(y);
            if(a == b) continue;
            fa[a] = b;        //将以a为首的链 连到b为首的链 
            sum[a] = siz[b]; //a到跟节点（b）的距离 = b的规模 
            siz[b] += siz[a]; //b 所在的规模 加入了a的规模 
            siz[a] = siz[b];
        }
        if(c == 'C') {
            int x = read(), y = read();
            int a = find(x), b = find(y);
            if(a != b) printf("-1\n");
            else printf("%d\n", abs(sum[x] - sum[y]) - 1);
        }
    }
    return 0;
}