hdu1962Corporative Network帶權回路

/*
    有N個企業，每個企業想要實現通信，要用線路來連接，線路的長度為abs(a-b)%1000;
    如果企業a 鏈接到了企業b 那么b就是the center of the serving!
    然后有兩種操作：
    E a ： 輸出企業a到serving center 的線路的距離
    I a, b  將企業a連接到企業 b，那么b就成為了serving center（之前連接a的企業，他們的serving center也變成了b） 
    
   思路：并查集！ （壓縮路徑時回溯求解） ！ 
*/ 
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define M 20005
using namespace std;
int n;
int f[M];
int ans[M];//節點 i到 serving center的距離！ 

int getFather(int x){
    if(x==f[x]) return x;
    int ff=getFather(f[x]);
    ans[x]+=ans[f[x]];//節點x到serving center 的距離要加上其父節點到serving center的距離！ 
    return f[x]=ff;
}

void Union(int a, int b){ 
    if(a==b) return;
    f[a]=b;
    ans[a]=abs(a-b) % 1000;
}

int main(){
   int t;
   char ch[3];
   cin>>t;
   while(t--){
      cin>>n;
      int a, b;
      memset(ans, 0, sizeof(ans));
      for(int i=1; i<=n; ++i)
         f[i]=i;
      while(cin>>ch && ch[0]!='O'){
          if(ch[0]=='E'){
             cin>>a;
             getFather(a);
             cout<<ans[a]<<endl;
          }
          else{
             cin>>a>>b;
             Union(a, b);
          }
      }
   }
   return 0;
}

?