考试的时候这道题没想出来，考完了在LCX的提示下想出来了。呵呵
树状数组。那怎么把这颗树拍平呢（转换成1维数组）？
其实很简单（当然是想到了才简单），从root开始dfs下去记录第一次访问u点时的时间戳为st[u]（下标），当访问完以u为根的所有子树以后要向上回溯的时候，在记录一个时间戳end[u]（下标），
这样，一棵树的所有顶点权值的和就是st[u]到end[u]的区间和，操作就和普通的树状数组一样了~
PS：注意读入，我这个蒟蒻把读入写错了，本机测试没事，上评测机就不行了，不知道为什么。。。
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #define N 1001000 5 using namespace std; 6 int head[N],next[N],to[N],d[N],cnt,num,st[N],end[N],n,m; 7 bool vis[N]; 8 void add(int u,int v) 9 { 10 to[cnt]=v; next[cnt]=head[u]; head[u]=cnt++; 11 } 12 void read() 13 { 14 memset(head,-1,sizeof head); 15 cnt=0; 16 for(int i=1,a,b;i<n;i++) 17 { 18 scanf("%d%d",&a,&b); 19 add(a,b); add(b,a); 20 } 21 } 22 void dfs(int u) 23 { 24 st[u]=++num; 25 vis[u]=true; 26 for(int i=head[u];~i;i=next[i]) 27 if(!vis[to[i]]) 28 dfs(to[i]); 29 end[u]=num; 30 } 31 int lowbit(int k) 32 { 33 return k&(-k); 34 } 35 void updata(int x,int nu) 36 { 37 while(x<=num) 38 { 39 d[x]+=nu; 40 x+=lowbit(x); 41 } 42 } 43 int getsum(int x) 44 { 45 int sum=0; 46 while(x) 47 { 48 sum+=d[x]; 49 x-=lowbit(x); 50 } 51 return sum; 52 } 53 void go() 54 { 55 memset(vis,0,sizeof vis); 56 num=0; 57 dfs(1); 58 for(int i=1;i<=n;i++) updata(i,1); 59 scanf("%d",&m); 60 int a;char b; 61 while(m--) 62 { 63 getchar(); 64 scanf("%c%d",&b,&a); 65 if(b=='C') 66 { 67 if(getsum(st[a])-getsum(st[a]-1)==1) 68 updata(st[a],-1); 69 else updata(st[a],1); 70 } 71 else printf("%d\n",getsum(end[a])-getsum(st[a]-1)); 72 } 73 } 74 int main() 75 { 76 while(scanf("%d",&n)!=EOF) 77 { 78 read(); 79 go(); 80 } 81 return 0; 82 }