PKU 1988 Cube Stacking

http://poj.org/problem?id=1988
n個のキューブに対して、以下のクエリを処理する。

・キューブXを含むスタックを、キューブYを含むスタックの上にのせる。
・キューブXの下に何個キューブあるか数える

これもユニオンファインドを使う。
あるキューブを含むスタックの親への距離と、親のもつ個の数が分かれば、そのキューブの子の数が分かる。
あとはそれをうまく処理する。

int un[30000];
int ch[30000];
int di[30000];

int find(int x){
  if(x==un[x])
    return x;
  int p=find(un[x]);
  di[x] += di[un[x]];
  return
    un[x] = p;
}

void unit(int a,int b){
  int ap=find(a);
  int bp=find(b);
  un[bp] = ap;
  di[bp] += ch[ap];  
  ch[ap] += ch[bp];
}


main(){
  int N=30000;
  rep(i,N){
    un[i]=i;
    ch[i]=1;
  }
  
  int p;
  cin >> p;
  rep(i,p){
    //rep(j,6) cout << j << ' ' << un[j] << ' ' << ch[j] << ' ' << di[j] << endl;
    char c;
    cin >> c;
    if(c=='M'){
      int x,y;
      cin >> x >> y;
      --x;--y;
      unit(x,y);
    }else{
      int q;
      cin >> q;
      --q;
      int pa=find(q);
      cout << ch[pa] - di[q] - 1<< endl;
    }
  }
}