边带权并查集用于维护相互连通的结点之间的权值。其中的难点在于分析路径压缩时对于结点的更新。
在分析一道题时，我们要清楚自己所要得到的信息，并找到其来源。在写程序之前，先分析确定边权（深度？子树大小？），再分析回溯过程中权值的更新方式。
这道题带来的困惑是，对于合并队伍，我们会把树根连在一起。对于连通性显然是没有影响的，但是我们丧失了被合并的队伍队首以下的距离。如果我们记录每个结点到父结点的距离呢？在合并时X的所有结点更新，似乎太浪费时间了，并且由于并查集由下向上传递，在查的时候我们无法找到子结点，因而这种方法不可取。
我们希望在合并的时候只改变X的树根的权值。我们可以用d[x]表示结点到父结点之间的距离。由于题目询问集合中元素的数量，我们需要size[x]维护字数大小，并不断更新。这样一来，在合并的时候，我们可以把Y字数大小叠加到X的d中，表示X与Y之间相隔了d[x]的距离，再把X的子树大小叠加到Y中。在路径压缩时，把距父结点的权值不断由上到下叠加得到。
题目
公元五八○一年，地球居民迁至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。
宇宙历七九九年，银河系的两大军事集*在巴米利恩星域爆发战争。泰山压顶集**宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集*点名将杨威利组织麾下三万艘战舰迎敌。
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成300003000030000列，每列依次编号为1,2,…,300001, 2, …,300001,2,…,30000。之后，他把自己的战舰也依次编号为1,2,…,300001, 2, …, 300001,2,…,30000，让第iii号战舰处于第iii列(i=1,2,…,30000)(i = 1, 2, …, 30000)(i=1,2,…,30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为Mi,jM_{i,j}Mi,j，含义为第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。
在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：Ci,jC_{i,j}Ci,j。该指令意思是，询问电脑，杨威利的第iii号战舰与第jjj号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。
最终的决战已经展开，银河的历史又翻过了一页……
输入输出格式
输入格式：
第一行有一个整数T(1≤T≤500,000)T(1 le T le 500,000)T(1≤T≤500,000)，表示总共有TTT条指令。
以下有TTT行，每行有一条指令。指令有两种格式：
Mi,jM_{i,j}Mi,j ：iii和jjj是两个整数(1≤i,j≤30000)(1 le i,j le 30000)(1≤i,j≤30000)，表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第iii号战舰与第jjj号战舰不在同一列。
Ci,jC_{i,j}Ci,j ：iii和jjj是两个整数(1≤i,j≤30000)(1 le i,j le 30000)(1≤i,j≤30000)，表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
输出格式：
依次对输入的每一条指令进行分析和处理：
如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第iii号战舰与第jjj号战舰之间布置的战舰数目。如果第iii号战舰与第jjj号战舰当前不在同一列上，则输出−1-1−1。
CODE
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int SIZE = 30005; 5 int fa[SIZE], d[SIZE], size[SIZE], t; //d记录到父节点距离 size记录子树大小 6 int get(int x){ 7 if(x == fa[x]) return x; 8 int root = get(fa[x]); 9 d[x] += d[fa[x]]; 10 return fa[x] = root; 11 } 12 13 void merge(int x, int y){ 14 x = get(x), y = get(y); 15 fa[x] = y; 16 d[x] += size[y]; 17 size[y] += size[x]; 18 return; 19 } 20 21 int main(){ 22 // freopen("galaxy1.in", "r", stdin); 23 cin >> t; 24 for(int i=1; i<SIZE; i++){ 25 fa[i] = i; 26 d[i] = 0; 27 size[i] = 1; 28 } 29 30 while(t--){ 31 char f; 32 int x, y; 33 scanf(" %c %d %d", &f, &x, &y); 34 switch(f){ 35 case 'M': 36 merge(x, y); 37 break; 38 case 'C': 39 if(get(x) != get(y)){ 40 printf("%d ", -1); 41 continue; 42 } 43 int ans = d[x] - d[y]; 44 ans = ans < 0 ? -ans : ans; 45 printf("%d ", ans - 1); 46 break; 47 } 48 49 } 50 return 0; 51 }