POJ.3321 Apple Tree

1.Problme
http://poj.org/problem?id=3321

2.Idea
A good editorail using BIT.

3.Source

 const int MAX_N = 100009;  
 int table[MAX_N+1];  
 int BIT[MAX_N+1];  
 int tos[MAX_N+1];  
 int idx[MAX_N+1];  
 bool noApple[MAX_N+1];  
 vector<int> G[MAX_N+1];  
 int N, counter;  
 inline int readint(){  
   int ret = 0, x;  
   while(x=getchar(), !('0'<=x&&x<='9'));  
   ret = (x&15);  
   while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + (x&15);  
   return ret;  
 }  
 inline int sum(int n){int _R=0;for(;n;n-=n&-n)_R+=BIT[n];return _R;}  
 inline int sum(int from, int to){return sum(to-1)-sum(from-1);}  
 inline void add(int n, int x){for(;n<=N;n+=n&-n)BIT[n]+=x;}  
 inline void dfs(int v){  
      int gv = G[v].size();  
      table[v] = counter++;  
      for(int i=0; i<gv; i++){  
           if(!table[G[v][i]]) dfs(G[v][i]);  
      }  
      tos[table[v]] = counter;  
 }  
 int main(){  
      N = readint();  
      for(int i=0, x, y; i<N-1; i++){  
           x = readint(), y = readint();  
           G[x].push_back(y); G[y].push_back(x);  
      }  
      counter = 1;  
      dfs(1);  
      int M = readint();  
      for(int i=0, x; i<M; i++){  
           char op;  
           scanf(" %c ",&op);  
           x = table[readint()];  
           if(op=='Q'){  
                printf("%d\n", tos[x]-x-sum(x,tos[x]));  
           }  
           else{  
                noApple[x] = !noApple[x];  
                add(x,noApple[x]?1:-1);  
           }  
      }  
      return 0;  
 }