HDU - 3635- Dragon Balls

Five hundred years later, the number of dragon balls will increase unexpectedly, so it’s too difficult for Monkey King(WuKong) to gather all of the dragon balls together.

His country has N cities and there are exactly N dragon balls in the world. At first, for the ith dragon ball, the sacred dragon will puts it in the ith city. Through long years, some cities’ dragon ball(s) would be transported to other cities. To save physical strength WuKong plans to take Flying Nimbus Cloud, a magical flying cloud to gather dragon balls.
Every time WuKong will collect the information of one dragon ball, he will ask you the information of that ball. You must tell him which city the ball is located and how many dragon balls are there in that city, you also need to tell him how many times the ball has been transported so far.
Input
The first line of the input is a single positive integer T(0 < T <= 100).
For each case, the first line contains two integers: N and Q (2 < N <= 10000 , 2 < Q <= 10000).
Each of the following Q lines contains either a fact or a question as the follow format:
T A B : All the dragon balls which are in the same city with A have been transported to the city the Bth ball in. You can assume that the two cities are different.
Q A : WuKong want to know X (the id of the city Ath ball is in), Y (the count of balls in Xth city) and Z (the tranporting times of the Ath ball). (1 <= A, B <= N)
Output
For each test case, output the test case number formated as sample output. Then for each query, output a line with three integers X Y Z saparated by a blank space.
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
题目传送门：HDU - 3635- Dragon Balls
题目大意： 先给一个数 t 表示有 t 组测试 然后 每组数据有两个数 n，m 分别表示一共有n个数，m次操作，T x，y 表示把含x的队伍移动到含y的队伍里面，Q x表示查询x然后需要输出x现在的祖先节点是谁，这个节点一共有几个成员，x被移动了几次；另外每组开始的时候需要输出Case x:（这是第几组测试）
解题思路
这个题真的是麻烦，还是带权并查集，记录祖先节点好办每次查找就行了，总共个数也好办开个数组就行了，每次记录该祖先节点的总结点数，一单合并只要祖先节点相加就可以了，就是移动的次数难受的一批，我刚开始直接开个数组存，但是发现不行如果1,2,4；现在移动的是2，那么只用2以上的节点的移动次数加一了，1就没变所以说还是需要改进。。。经过我不懈的思考查找CSDN终于发现了一个秒方法，就是每次改变值把祖先节点的移动次数加一就行，然后查找节点的时候在回溯的工程中一个个的都加上，真实妙呀！！！

#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

int fa[20000],sum[20000];
int ch[20000];
int find(int x)
{
	if(x!=fa[x])
	{
		int s=fa[x];
		fa[x]=find(s);
		ch[x]+=ch[s];//回溯的时候更新变化数 
	}
	return fa[x];
}
void join(int x,int y)
{
	int xx=find(x);
	int yy=find(y);
	if(xx!=yy)
	{
	    sum[yy]+=sum[xx];//总结点数相加 
		fa[xx]=yy;	
		ch[xx]++;//后面的主节点变化数+1； 
	}
}

int main()
{
	int t,xx,y,n,m;
	char c;
	scanf("%d",&t);
	int k=1;
	
	while(t--)
	{
	    int flag=1;
		scanf("%d%d",&n,&m);
		printf("Case %d:\n",k++);
		for(int i=1;i<=n;i++)
		{
			sum[i]=1;
			ch[i]=0;
			fa[i]=i;
		}
		while(m--)
		{
			scanf(" %c",&c);
			if(c=='T')
			{
				scanf("%d%d",&xx,&y);
				join(xx,y);
			}
			else{
				scanf("%d",&xx);
				int xxx=find(xx);
				printf("%d %d %d\n",xxx,sum[xxx],ch[xx]);
			}
		}
	}
	return 0;
}