银河英雄传说 带权并查集

题意：
有一个划分为N列的星际战场, 各列依次编号为 1, 2, ···, N. 有 N 艘战舰, 也依次编号为 1 - N, 初始时, 第 i 号战舰在第 i 列.

T条指令, 有两种格式.

1. M i j, 表示让第 i 号战舰所在列的全部战舰保持原有的顺序, 接在第 j 号战舰所在列的尾部.

2. C i j, 表示询问第 i 号战舰与第 j 号战舰是否处在同一列中, 如果在同一列中, 他们之间间隔了多少艘战舰.

N <= 30000, T <= 5e5.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=30010;
int fa[maxn];//并查集数组
int Size[maxn];//这个集合的节点个数
int d[maxn];//i到 fa[i]的距离

void Init(){
    for(int i = 0; i < maxn; ++i){
        Size[i] = 1;
        d[i] = 0;
        fa[i] = i;
    }
}

inline int Find(int v)
{
	if(fa[v]==v) return v;
	int root=Find(fa[v]);
	d[v]+=d[fa[v]];
	return fa[v]=root;
}

void Merge(int x, int y){
    x = Find(x), y = Find(y);
    fa[x] = y;
    d[x] = Size[y];
    Size[y] += Size[x];
}
int main()
{
    Init();
    int t;
    scanf("%d", &t);
    int x, y;
    char cmd;
    while(t--){
        getchar();
        scanf("%c%d%d", &cmd, &x, &y);
        if(cmd == 'M'){
            Merge(x, y);
        }
        else{
            if(Find(x) == Find(y)){
                printf("%d\n", abs(d[x] - d[y]) - 1);
            }
            else{
                printf("-1\n");
            }
        }
    }
    return 0;
}