1 /* 2     有N个企业，每个企业想要实现通信，要用线路来连接，线路的长度为abs(a-b)%1000; 3     如果企业a 链接到了企业b 那么b就是the center of the serving! 4     然后有两种操作： 5     E a ： 输出企业a到serving center 的线路的距离 6     I a, b  将企业a连接到企业 b，那么b就成为了serving center（之前连接a的企业，他们的serving center也变成了b）  7      8    思路：并查集！ （压缩路径时回溯求解） ！  9 */ 10 #include<iostream>11 #include<cstring>12 #include<cmath>13 #include<cstdio>14 #define M 2000515 using namespace std;16 int n;17 int f[M];18 int ans[M];//节点 i到 serving center的距离！ 19 20 int getFather(int x){21     if(x==f[x]) return x;22     int ff=getFather(f[x]);23     ans[x]+=ans[f[x]];//节点x到serving center 的距离要加上其父节点到serving center的距离！ 24     return f[x]=ff;25 }26 27 void Union(int a, int b){ 28     if(a==b) return;29     f[a]=b;30     ans[a]=abs(a-b) % 1000;31 }32 33 int main(){34    int t;35    char ch[3];36    cin>>t;37    while(t--){38       cin>>n;39       int a, b;40       memset(ans, 0, sizeof(ans));41       for(int i=1; i<=n; ++i)42          f[i]=i;43       while(cin>>ch && ch[0]!=‘O‘){44           if(ch[0]==‘E‘){45              cin>>a;46              getFather(a);47              cout<<ans[a]<<endl;48           }49           else{50              cin>>a>>b;51              Union(a, b);52           }53       }54    }55    return 0;56 }