【NOIP模拟赛】Hzwer的陨石

2014年10月31日1,2270

题目描述:

经过不懈的努力,Hzwer召唤了很多陨石。已知Hzwer的地图上共有n个区域,且一开始的时候第i个陨石掉在了第i个区域。有电力喷射背包的ndsf很自豪,他认为搬陨石很容易,所以他将一些区域的陨石全搬到了另外一些区域。

在ndsf愉快的搬运过程中,Hzwer想知道一些陨石的信息。对于Hzwer询问的每个陨石i,你必须告诉他,在当前这个时候,i号陨石在所在区域x、x区域共有的陨石数y、以及i号陨石被搬运的次数z。

输入描述:

输入的第一行是一个正整数T。表示有多少组输入数据。

接下来共有T组数据,对于每组数据,第一行包含两个整数:N和Q。

接下来Q行,每行表示一次搬运或一次询问,格式如下:

T A B:表示搬运,即将所有在A号球所在地区的陨石都搬到B号球所在地区去。

Q A:悟空想知道A号陨石的x,y,z。

输出描述:

对于第i组数据,第一行输出“Case i:”接下来输出每一个询问操作的x,y,z,每一个询问操作的答案占一行。每组数据之间没有空行。

样例输入:

2

3 3

T 1 2

T 3 2

Q 2

3 4

T 1 2

Q 1

T 1 3

Q 1

样例输出:

Case 1:

2 3 0

Case 2:

2 2 1

3 3 2

数据范围:

20%的数据保证:0≤T≤20,2<N<=100,2<Q<=100。

100%的数据保证:0≤T≤100,2<N<=10000,2<Q<=10000。

对于所有数据保证搬运操作中AB在N的范围内且所在区域不相同。

题解

带权并查集。。。

移动次数标记在每个集合的根

压缩路径时,每个点先获得它父亲的移动次数,再换父亲