树映射到树状数组上
非常好的题目，给了我很多启发
题目要求动态求一个棵子树的节点个数
不禁联想到了前缀和，只要我们能用一个合适的优先级表示每个顶点，那么就好做了
我们可以考虑将子树表示成区间的形式
这个子树的根节点显然是区间的右端点，那么左端点一定是子树中编号最小的那个
这样问题就转化为区间求和，单点修改的问题了
很容易想到树状数组
我们可以用后序遍历树，这样映射到树状数组之后就好办了
1 type link=^node; 2 node=record 3 po:longint; 4 next:link; 5 end; 6 var w:array[0..100100] of link; 7 c,h,f,a:array[0..100100] of longint; 8 v:array[0..100100] of boolean; 9 t,r,n,m,i,x,y:longint; 10 ch:char; 11 12 function lowbit(x:longint):longint; 13 begin 14 exit(x and (-x)); 15 end; 16 17 procedure add(x,y:longint); 18 var p:link; 19 begin 20 new(p); 21 p^.po:=y; 22 p^.next:=w[x]; 23 w[x]:=p; 24 end; 25 26 procedure dfs(i:longint); //映射 27 var tmp,y:longint; 28 p:link; 29 begin 30 v[i]:=true; 31 p:=w[i]; 32 tmp:=n+1; 33 while p<>nil do 34 begin 35 y:=p^.po; 36 if not v[y] then 37 begin 38 dfs(y); 39 if tmp>f[y] then tmp:=f[y]; 40 end; 41 p:=p^.next; 42 end; 43 inc(t); 44 h[i]:=t; 45 if tmp<>n+1 then 46 f[i]:=tmp 47 else f[i]:=h[i]; 48 end; 49 50 procedure work(x,f:longint); 51 begin 52 while x<=n do 53 begin 54 c[x]:=c[x]+f; 55 x:=x+lowbit(x); 56 end; 57 end; 58 59 function ask(x:longint):longint; 60 begin 61 ask:=0; 62 while x>0 do 63 begin 64 ask:=ask+c[x]; 65 x:=x-lowbit(x); 66 end; 67 end; 68 69 begin 70 readln(n); 71 for i:=1 to n-1 do 72 begin 73 readln(x,y); 74 add(x,y); 75 add(y,x); 76 a[i]:=1; 77 end; 78 a[n]:=1; 79 dfs(1); 80 for i:=1 to n do 81 work(i,1); 82 readln(m); 83 for i:=1 to m do 84 begin 85 readln(ch,r); 86 if ch='Q' then 87 begin 88 x:=f[r]; 89 y:=h[r]; 90 writeln(ask(y)-ask(x-1)); 91 end 92 else begin 93 x:=h[r]; 94 if a[x]=0 then work(x,1) //细节题目要求没苹果的时候加苹果 95 else work(x,-1); 96 a[x]:=a[x] xor 1; 97 end; 98 end; 99 end.
type link=^node;
node=record
po:longint;
next:link;
end;
var w:array[0..100100] of link;
c,h,f,a:array[0..100100] of longint;
v:array[0..100100] of boolean;
t,r,n,m,i,x,y:longint;
ch:char;
function lowbit(x:longint):longint;
begin
exit(x and (-x));
end;
procedure add(x,y:longint);
var p:link;
begin
new(p);
p^.po:=y;
p^.next:=w[x];
w[x]:=p;
end;
procedure dfs(i:longint); //映射
var tmp,y:longint;
p:link;
begin
v[i]:=true;
p:=w[i];
tmp:=n+1;
while p<>nil do
begin
y:=p^.po;
if not v[y] then
begin
dfs(y);
if tmp>f[y] then tmp:=f[y];
end;
p:=p^.next;
end;
inc(t);
h[i]:=t;
if tmp<>n+1 then
f[i]:=tmp
else f[i]:=h[i];
end;
procedure work(x,f:longint);
begin
while x<=n do
begin
c[x]:=c[x]+f;
x:=x+lowbit(x);
end;
end;
function ask(x:longint):longint;
begin
ask:=0;
while x>0 do
begin
ask:=ask+c[x];
x:=x-lowbit(x);
end;
end;
begin
readln(n);
for i:=1 to n-1 do
begin
readln(x,y);
add(x,y);
add(y,x);
a[i]:=1;
end;
a[n]:=1;
dfs(1);
for i:=1 to n do
work(i,1);
readln(m);
for i:=1 to m do
begin
readln(ch,r);
if ch='Q' then
begin
x:=f[r];
y:=h[r];
writeln(ask(y)-ask(x-1));
end
else begin
x:=h[r];
if a[x]=0 then work(x,1) //细节题目要求没苹果的时候加苹果
else work(x,-1);
a[x]:=a[x] xor 1;
end;
end;
end.