1有标号为1到n的n个龙珠，分别放在对应标号为1到n的n个城市里。 2下面有两种操作: 3T A B表示把A龙珠所在城市的所有龙珠都转移到B龙珠所在的城市中 4Q A 表示查询A，需要知道A龙珠现在所在的城市，A所在的城市有几颗龙珠，A转移到这个城市移动了多少次,分别输出3个整数，表示上述信息。
前两个用普通并查集就能算出来，移动次数不好维护；
如果我们不进行路径压缩，那么查询点的深度即是移动的次数，因为每移动一次父节点就下降一层，深度+1；
但不路径压缩的话就会超时，所以我们要把点的深度记录下来；；
1#include <cstdio> 2#include <algorithm> 3#include <iostream> 4 5using namespace std; 6int ans[100000] ,ansn[100000] ,pre[100000]; 7 8void init( int x){ 9 for( int i = 0 ; i<=x ;i++){ 10 pre[i] = i; 11 ans[i] = 0; 12 ansn[i] = 1; 13 } 14} 15 16int find( int a){ 17 /* int r=a; //刚开始这样记录深度ans[a]，但是这样不对，这样只是路径压缩一次ans[n]++，但实际上一次可能压缩很多层，所以应该是加上上一层的压缩层数 18 while( pre[a]!=a){ 19 a=pre[a]; 20 } 21 int t; 22 while( pre[r]!=a){ 23 ans[r]++; 24 t= pre[r]; 25 pre[r] =a; 26 r=t; 27 }*/ 28 if( a == pre[a] )return a; 29 else{ 30 int tmp= pre[a]; 31 pre[a] = find( pre[a]); 32 ans[a] += ans[tmp]; 33 } 34 return pre[a]; 35} 36 37int add( int a ,int b){ 38 int x=find(a); 39 int y=find(b); 40 if( x != y){ 41 pre[x] = y; 42 ans[x] = 1; 43 ansn[y] += ansn[x]; 44 ansn[x] =0; 45 } 46} 47 48int main( ){ 49 int ks=0, T; 50 scanf("%d",&T); 51 while( T--){ 52 printf("Case %d:\n",++ks); 53 int n,m; 54 scanf("%d%d" ,&n ,&m); 55 init( n); 56 while( m--){ 57 char op[10]; 58 int a,b; 59 scanf("%s",op); 60 if( op[0] == 'T'){ 61 scanf("%d%d" ,&a,&b); 62 add( a,b); 63 } 64 if( op[0] == 'Q'){ 65 scanf("%d" ,&a); 66 int b=find(a); 67 printf("%d %d %d\n" ,b ,ansn[b] ,ans[a]); 68 } 69 } 70 } 71 return 0; 72}