這道題題意很難懂，大意是有N個(gè)公司，每個(gè)公司有一個(gè)center，最初每個(gè)公司的center都在自己公司，然后有M次操作，每次操作 A , B (A保證是一個(gè)集合的center，B不一定) 表示將A所在的集合并到B所在的集合，且B的center成為了A的center。每次操作后兩個(gè)公司的線的距離增加abs(A-B)%1000;
Sample Input: (E P表示查詢P距離自己center的線的長度，I P Q 表示合并 P ,Q);
1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O
Sample Output:
0
2
3
5
Code:
#include <cstdio>
#include <iostream>
#define M 20010
using namespace std;
struct Node{
int father,num;
}a[M];
void initial(int n){
int i;
for(i = 1;i <= n; i++){
a[i].father = i;
a[i].num = 0;
}
}
int find(int n){
int tep,m = n;
if(n == a[n].father) return n;
find(a[n].father); //遞歸查找n的祖先
a[n].num += a[a[n].father].num; //n的直需要更新(加上n的父親的值)
a[n].father = a[a[n].father].father;
}
int main()
{
int T,n,i,j,k;
char order[3];
scanf("%d",&T);
while(T--){
scanf("%d",&n);
initial(n);
while(scanf("%s",order)){
if(order[0]== 'O') break;
if(order[0] == 'E'){
scanf("%d",&k);
find(k);
printf("%d\n",a[k].num);
}
else{
scanf("%d%d",&j,&k);
int dis = abs(j-k)%1000;
a[j].num = dis; //該值dis為j的值
a[j].father = k; //k成為了j的父親
}
}
}
}