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; } } }