树映射到树状数组上
非常好的题目，给了我很多启发
题目要求动态求一个棵子树的节点个数
不禁联想到了前缀和，只要我们能用一个合适的优先级表示每个顶点，那么就好做了
我们可以考虑将子树表示成区间的形式
这个子树的根节点显然是区间的右端点，那么左端点一定是子树中编号最小的那个
这样问题就转化为区间求和，单点修改的问题了
很容易想到树状数组
我们可以用后序遍历树，这样映射到树状数组之后就好办了
type link=^node;
node=record
po:longint;
next:link;
end;
var w:array[..] of link;
c,h,f,a:array[..] of longint;
v:array[..] 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+;
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+ 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:=;
while x> do
begin
ask:=ask+c[x];
x:=x-lowbit(x);
end;
end; begin
readln(n);
for i:= to n- do
begin
readln(x,y);
add(x,y);
add(y,x);
a[i]:=;
end;
a[n]:=;
dfs();
for i:= to n do
work(i,);
readln(m);
for i:= to m do
begin
readln(ch,r);
if ch='Q' then
begin
x:=f[r];
y:=h[r];
writeln(ask(y)-ask(x-));
end
else begin
x:=h[r];
if a[x]= then work(x,) //细节题目要求没苹果的时候加苹果
else work(x,-);
a[x]:=a[x] xor ;
end;
end;
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.