这道题说，在很久很久以前，有一个故事。故事的名字叫龙珠。后来，龙珠不知道出了什么问题，从7个变成了n个。
在悟空所在的国家里有n个城市，每个城市有1个龙珠，第i个城市有第i个龙珠。
然后，每经过一段时间，城市i的所有的龙珠都会被转移到城市j中。
现在有两种操作：
1. T A B，表示将A龙珠所在城市的所有龙珠全部转移到B龙珠所在城市去。
2. Q A，表示询问A龙珠所在的城市X，以及X城市有几个龙珠，A龙珠被转移了几次。
输入：
第一行输入1个整型数字t，表示一共t组测试样例。
接下来，每组样例第一行包含2个整型数字n，m，表示共有n个城市，m次操作。
操作有T A B，以及Q A两种，具体含义看上面。
输出：
当输入Q A时，输出所询问的数据。每次输出占一行。
说实话，我写这道题的时候，感觉这道题相当有问题。
因为我做不出来，所以依然可耻地看了题解。但是题解中居然是用了并查集！
并查集是有问题的。因为在T A B时，它的含义是龙珠A移动到龙珠B那里，也就是说，之后的T B A 是没有意义的。但实际上，如果是按照城市A的龙珠转移到城市B去，那么实际上之后再进行T B A是有意义的。所以，是不能使用并查集的。
后来我发现我读错题了……
所以，你可以忽略以上六行的文字，包括这一行。
分析：
正确理解了题意以后，发现这是一道加权并查集。而且每个节点有两个权值。一个是所在城市的龙珠数量sum[]，一个是移动次数mv[]。
所以可以开3个数组。然后注意一下每个数据的计算方式就行了。
初始化时，每个龙珠的父节点是自己，所在城市的龙珠数量为1，移动次数为0。
接下来，每移动一次，所移动的龙珠集合的根节点的移动次数从0变成1，其它龙珠的移动次数依次变成他的父节点的移动次数+自己的移动次数，即mv[x] = mv[fx]+mv[x]（这一句不理解不要紧，自己在纸上推一下，注意路径压缩）。 而且是递归修改，从根节点开始修改，然后是以根节点为父节点的节点，然后是依次递归回溯。这样可以在我们用到某个节点的时候，一次将这个节点更新成功，而如果每次修改时都更改所有被修改的节点，那么许多节点都会被修改多次。这样，所必须的修改就是将被合并的根节点修改一次即可。
具体见代码——
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int N = 10010; 8 9 int n, m, t;10 int sum[N], fm[N], mv[N]; //分别表示龙珠所在地的龙珠数量和，某龙珠的父节点，某龙珠被移动的次数11 int a, b;12 char s[2];13 14 void init()15 {16 scanf("%d%d", &n, &m);17 for(int i = 0; i <= n; i++) //初始化18 {19 fm[i] = i;20 sum[i] = 1;21 mv[i] = 0;22 }23 }24 25 int mfind(int x) //合并与查询时都使用26 {27 if(x == fm[x]) return x;28 int fx = fm[x];29 fm[x] = mfind(fm[x]);30 mv[x] += mv[fx]; //关键点，龙珠x被移动的次数31 return fm[x];32 }33 34 void mmerge(int x, int y)35 {36 int fx = mfind(x);37 int fy = mfind(y);38 if(fx != fy)39 {40 fm[fx] = fy;41 sum[fy] += sum[fx]; //计算龙珠fy处的龙珠总和42 mv[fx] = 1; //根节点首次被移动，所以移动次数为143 }44 }45 46 void work()47 {48 while(m--)49 {50 scanf("%s", s);51 if(s[0] == 'Q')52 {53 scanf("%d", &a);54 int fa = mfind(a);55 printf("%d %d %d\n", fa, sum[fa], mv[a]);56 }57 else if(s[0] == 'T')58 {59 scanf("%d%d", &a, &b);60 mmerge(a, b);61 }62 }63 }64 65 int main()66 {67 //freopen("test.in", "r", stdin);68 while(~scanf("%d", &t))69 {70 for(int tm = 1; tm <= t; tm++)71 {72 init();73 printf("Case %d:\n", tm);74 work();75 }76 }77 }