キューブゲーム(銀河英雄伝説)(そして調査集)

キューブゲーム(cubes.pas/c/cpp)【タイトル説明】AちゃんとBちゃんがキューブゲームをしています.1からn(1<=n<=30000)のn個のブロックが地面に置かれている.各立方柱を構成します.ゲーム開始後、AちゃんはBちゃんにp(1<=p<=10000000)個のコマンドを出す.1、移動(M):Xを含む立方柱をYを含む立方柱に移動します.2、統計(C):Xを含む立方柱のうち、Xの下にあるブロックの数を統計する.プログラムを書いてBさんのゲームを完成させます.【入力データ】1行目にPが入力され、その後、P行毎に1つの指令が入力される.形式は「MX Y」または「CX」である.立方柱を自分の頭に置く命令がないことを保証します.【出力データ】各行について、統計指令毎に、その結果を出力する.【サンプル入力】6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4【サンプル出力】1 0 2【データ範囲】40%のデータに対してn,P≦200.60%のデータに対してn,P≦2000であった.100%のデータに対してn,P≦100000であった.
模擬試合の試験問題で、タッチした「銀河英雄伝説」(WikiOI 1540)とほぼ一致していたので、できると思っていたのに、長い間悩んでいたので、この問題を再収録しました.(銀河英雄伝説:http://codevs.cn/problem/1540/)
各ブロックの最後に更新されたときに指向された親ノードを集計で記録し,問い合わせ時に更新する.前回記録されたときは、必ず親ノードがその時点で一番下のブロックであったので、親ノードの下に増加したブロック数もそのノードの下に増加したブロックの数であり、find関数にこの操作を加えればよい.

program mys;
var i,k,x,y,rx,ry,p:longint;
f,d,sum:array[0..60000]of longint;
ch:char;

function find(x:longint):longint;
var t,y:longint;
begin 
if f[x]<>x then 
begin 
t:=f[x];
f[x]:=find(f[x]);
d[x]:=d[x]+d[t];
end;
exit(f[x]);
end;

begin 
assign(input,'cubes.in'); reset(input);
assign(output,'cubes.out'); rewrite(output);
readln(p);
for i:=1 to 30000 do 
begin 
f[i]:=i; d[i]:=0; sum[i]:=1;
end;
for i:=1 to p do 
begin
read(ch);
if ch='M' then read(x,y)
else read(x);
readln;

if ch='M' then 
begin 
rx:=find(x);
ry:=find(y);
f[rx]:=ry;
d[rx]:=sum[ry];
sum[ry]:=sum[ry]+sum[rx];
end
else 
begin 
rx:=find(x);
writeln(d[x]);
end;

end;
close(input);
close(output);
end.