题目描述 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:\n",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\n",xx,b[xx],a[x]);}}}return 0; }
