3.xth的苹果树(apple.pas/c/cpp)
描述
xth种了一棵苹果树，这棵树由n个节点构成，中间有树枝连接，苹果都会长在节点上，并且不会有两个苹果长在同一个节点上。Xth想知道某个子树上有多少个苹果，你能帮帮他吗？（1号节点为跟）
输入格式(apple.in)
第一行：一个整数n，表示苹果树有n个节点。
以下n-1行：每行两个整数u、v，表示u、v两节点间有树枝相连。
第n+1行：一个整数m，表示有m个询问或操作。
以下m行：一个字符（’C’或’Q’）和一个整数x。‘C’表示将x节点处的苹果有无情况取反。‘Q’表示询问以x为根的子树中苹果的个数。
注：苹果树开始时是长满苹果的。
输出格式(apple.out)
对于每一个询问输出一行，一个整数，表示苹果数。
输入样例
3
1 2
1 3
3
Q 1
C 2
Q 1
输出样例
3
2
数据规模
N<=100 000,M<=100000
树的遍历+树状数组。
然后，首先根据给出的条件，建树。
然后，对树进行前序遍历，这样可以发现，每一个非叶子节点都会连着一段节点，而这一段节点就是他的儿子，所以，用树状数组处理，每一次求出询问节点和往后找的第一个不是他儿子的节点之间一段的和（当然，也可以不用树状数组，直接求似乎也过了）。
这个题好想，不好写。
树形恐惧症患者悠悠的飘过。
type
ll=record
l,r,v:longint;
end;
list=record
y,n:Longint;
end;
var
i,j,k,n,m:longint;
s,d,f:array[0..1000001] of longint;
b:array[0..1000001] of ll;
c:array[0..1000001] of list;
aa,bb,cc:longint;
tmp,o,tot,x:longint;
ch:char;
function lowbit(x:Longint):longint;
begin
exit(x and (-x));
end;
procedure add(x,k:longint);
begin
while x<=tot do
begin
s[x]:=s[x]+k;
x:=x+lowbit(x);
end;
end;
procedure addd(aa,bb:longint);
begin
inc(o);
c[o].y:=bb;
c[o].n:=f[aa];
f[aa]:=o;
end;
function sum(x:longint):Longint;
begin
sum:=0;
//if x=0 then exit(0);
while x>0 do
begin
sum:=sum+s[x];
x:=x-lowbit(x);
end;
end;
procedure dfs(fa,i:longint);
var
ii,jj,t,v:longint;
begin
t:=f[i];
inc(tot);
d[i]:=tot;
v:=tot;
while t<>0 do
begin
if c[t].y<>fa then
dfs(i,c[t].y);
t:=c[t].n;
end;
b[v].r:=tot;
b[v].v:=1;
end;
procedure main;
begin
readln(n);
o:=0;
fillchar(f,sizeof(f),0);
for i:=1 to n-1 do
begin
readln(aa,bb);
addd(aa,bb);
addd(bb,aa);
end;
tot:=0;
dfs(0,1);
for i:=1 to n do
add(i,1);
readln(m);
for i:=1 to m do
begin
readln(ch,x);
if ch='C' then
begin
if b[d[x]].v=1 then add(d[x],-1)
else add(d[x],1);
b[d[x]].v:=1-b[d[x]].v;
end
else
writeln(sum(b[d[x]].r)-sum(d[x]-1));
end;
end;
begin
assign(input,'apple.in');reset(input);
assign(output,'apple.out');rewrite(output);
main;
close(input);
close(output);
end.