题目大意：初始时，有n个龙珠，编号从1到n，分别对应的放在编号从1到n的城市中。现在又2种操作：T A B，表示把A球所在城市全部的龙珠全部转移到B城市。（第一次时，因为A球所在的城市只有一个球，，所以只移动1个，如果有多个，则全部移动）。
Q A，表示查询A。要求得到的信息分别是：A现在所在的城市，A所在城市的龙珠数目，A转移到该城市移动的次数（如果没有移动就输出0）
思路:并查集，难点在于求龙珠的转移次数，可以在路径压缩的过程中沿着递归路径累加。
//Accepted1740 KB530 ms#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N = 1e4+1e2;struct node{int cnt;int fa;}ball[N];int num[N];int n,q;void ini(){for(int i=1;i<=n;i++){num[i]=1;ball[i].fa=i;ball[i].cnt=0;}}int getf(int v){if(v==ball[v].fa) return v;int tmp=ball[v].fa;ball[v].fa=getf(ball[v].fa);ball[v].cnt+=ball[tmp ].cnt;return ball[v].fa;}void Merge(int x,int y){int t1=getf(x);int t2=getf(y);ball[t1].fa=t2;ball[t1].cnt++;num[t2]+=num[t1];}int main(){int T;scanf("%d",&T);for(int cas=1;cas<=T;cas++){printf("Case %d:\n",cas);scanf("%d%d",&n,&q);ini();while(q–){char op[5];scanf("%s",op);if(op[0]=='T'){int a,b;scanf("%d%d",&a,&b);Merge(a,b);}else{int p;scanf("%d",&p);int city=getf(p);printf("%d %d %d\n",city,num[city],ball[p].cnt);}}}return 0;}
我们大都接受的是正面的教育，
