题目大意
有标号为1到n的n个龙珠，分别放在对应标号为1到n的n个城市里。
下面有两种操作:
- T A B表示把A龙珠所在城市的所有龙珠都转移到B龙珠所在的城市中
- A 表示查询A，需要知道A龙珠现在所在的城市，A所在的城市有几颗龙珠，A转移到这个城市移动了多少次,分别输出3个整数，表示上述信息。
解题思路
本题可以通过带权并查集来解决。可以发现，将集合a的父节点挂到集合b的父节点上，则属于集合a的节点的移动次数都要+1，而属于集合b的节点的移动次数无需改变，合并后的集合的节点数量等于两个集合的节点数量之和。对于查询操作，第一个相当于是询问父节点；第二个问集合元素个数，只要在合并的时候让两个集合数量相加即可；
重点就是第三个，如何计算移动次数了。可以把需要移动的集合的父节点挂到目标集合的父节点上，然后更新合并后的子节点的值，令需要移动的集合的子节点都加上1。这个可以在路径压缩的过程中，把需要移动的集合的父节点处的sum值置成1，而目标集合的父节点置成0来实现。
代码
const int maxn = 1e4+10;
int p[maxn], num[maxn], sum[maxn];
int find(int x) {
if (p[x]!=x) {
int tmp = p[x];
p[x] = find(p[x]);
sum[x] += sum[tmp];
}
return p[x];
}
int main(void) {
int t, kase = 1; scanf("%d",&t);
while(t--) {
int n,q; scanf("%d%d",&n,&q);
printf("Case %d:
",kase++);
for (int i = 0; i<=n; ++i) {
p[i] = i; num[i] = 1; sum[i] = 0;
}
char ch[3]; int a, b;
while(q--) {
scanf("%s",ch);
if(ch[0]=='T') {
scanf("%d%d",&a,&b);
int fa = find(a), fb = find(b);
if (fa!=fb) {
p[fa] = fb;
sum[fa] = 1;
num[fb] += num[fa];
}
}
else {
scanf("%d",&b); find(b);
printf("%d %d %d
",find(b),num[find(b)],sum[b]);
}
}
}
return 0;
}