洛谷 P1196 [NOI2002]银河英雄传说 （进阶指南，带边权的并查集）

算法竞赛进阶指南，196页，抄书上的代码。带边权的并查集。

本题要点：
1、 增加两个数组：
int d[MaxN]; // d[x] 表示x与fa[x] 之间的权值之和;
int size[MaxN]; // size[i] 表示以i点为父节点的集合 一共有多少个元素，也就是集合的大小;
2、每一次 查询，执行路径压缩的时候，这条链路上的所有点的 d 值。具体看 get 函数;
3、 每一次合并（将x为根的集合 加入到 以 y点为根的集合），
a）更新 d[x] 的值，d[x] = size[y]
b）更新 size[y] 的值，size[y] += size[x]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
const int MaxN = 300010;
int T;
int fa[MaxN];
int size[MaxN];	// size在每个树根记录集合的大小
int d[MaxN];	// d[x] 表示x与fa[x] 之间的权值之和int get(int x)
{
    if(x == fa[x]){
    return x;}int root = get(fa[x]);d[x] += d[fa[x]];return fa[x] = root;
}void merge(int x, int y)
{
    x = get(x), y = get(y);fa[x] = y;d[x] = size[y];size[y] += size[x];
}int main()
{
    for(int i = 1; i < MaxN; ++i){
    size[i] = 1;fa[i] = i;}char cmd[2] = {
    0};int a, b;scanf("%d", &T);while(T--){
    scanf("%s%d%d", cmd, &a, &b);if(cmd[0] == 'C'){
    int x = get(a), y = get(b);	if(x == y){
    printf("%d\n", abs(d[a] - d[b]) - 1);}else{
    printf("-1\n");}}else if(cmd[0] == 'M'){
    merge(a, b);	}}return 0;
}/* 4 M 2 3 C 1 2 M 2 4 C 4 2 *//* -1 1 */