题目描述 Description
经过不懈的努力，Hzwer召唤了很多陨石。已知Hzwer的地图上共有n个区域，且一开始的时候第i个陨石掉在了第i个区域。有电力喷射背包的ndsf很自豪，他认为搬陨石很容易，所以他将一些区域的陨石全搬到了另外一些区域。
在ndsf愉快的搬运过程中，Hzwer想知道一些陨石的信息。对于Hzwer询问的每个陨石i，你必须告诉他，在当前这个时候，i号陨石在所在区域x、x区域共有的陨石数y、以及i号陨石被搬运的次数z。
输入描述 Input Description
输入的第一行是一个正整数T。表示有多少组输入数据。
接下来共有T组数据，对于每组数据，第一行包含两个整数：N和Q。
接下来Q行，每行表示一次搬运或一次询问，格式如下：
T A B：表示搬运，即将所有在A号球所在地区的陨石都搬到B号球所在地区去。
Q A：悟空想知道Ａ号陨石的x，y，z。
输出描述 Output Description
对于第ｉ组数据，第一行输出“Case i：”接下来输出每一个询问操作的x，y，z，每一个询问操作的答案占一行。每组数据之间没有空行。
样例输入 Sample Input
2
3 3
T 1 2
T 3 2
Q 2
3 4
T 1 2
Q 1
T 1 3
Q 1
样例输出 Sample Output
Case 1：
2 3 0
Case 2：
2 2 1
3 3 2
数据范围及提示 Data Size & Hint
20%的数据保证：0≤T≤20，2＜N＜＝100，2＜Q＜＝100。
100%的数据保证：0≤T≤100，2＜N＜＝10000，2＜Q＜＝10000。
对于所有数据保证搬运操作中AB在Ｎ的范围内且所在区域不相同。
思路：
加权并查集；
移动次数标记在根上；
路径压缩时，每个点先获得父亲的移动次数在压缩路径。
代码：
#include<cstdio> #include<cstring> #define maxn 10001 using namespace std; int fa[maxn],a[maxn],b[maxn],n,m,t,tot; int find(int x) { if(x==fa[x]) return x; int xx=fa[x],yy=find(fa[x]); if(xx!=yy) a[x]+=a[xx]; fa[x]=yy; return fa[x]; } int main() { int i,j; scanf("%d",&t); for(tot=1;tot<=t;tot++) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) fa[i]=i,b[i]=1; printf("Case %d: ",tot); memset(a,0,sizeof(a)); for(i=1;i<=m;i++) { char s[10]; int x,y; scanf("%s",s); if(s[0]=='T') { scanf("%d%d",&x,&y); int xx=find(x),yy=find(y); a[xx]++; fa[xx]=yy; b[yy]+=b[xx]; } else { scanf("%d",&x); int xx=find(x); printf("%d %d %d ",xx,b[xx],a[x]); } } } return 0; }