poj上面的一道求子树上苹果的题目，网上看了很多题解，下面我来回忆一下，基本来源于大神的微博，http://blog.csdn.net/zhang20072844，我来做个搬运工。
先将树的n条边上节点重新标号，让每一棵子树上的节点编号构成一个连续的区间，然后利用dfs将第i个节点表示的区间下限，上限存进数组low[u],high[u]。树状数组c[i]=a[i-2^k+1]+a[i-2^k+2]+.....a[i]，也就是i-2^k+1到i之间的苹果总数，每一个a[i]表示树上一个分叉，i是经过重新标号后的表示节点的值。
可以通过add（low[i],1）为第i（原苹果树中标号）个节点增加一个苹果，同时更新树状数组中和i（也就是元素a[low[i]]有关的c[j]值，这样查询low[i]到high[i]区间范围内的苹果数目便可以通过sum（high[i])-sum(low[i]-1）,其中sum（t）表示a[i]+a[2].....a[t]之和也就是这些节点上苹果数目。
1 #include<stdio.h> 2 #include<string.h> 3 #define N 100010 4 5 typedef struct 6 { 7 int to,next; 8 } Edge; 9 Edge edge[N]; 10 int low[N],high[N],vis[N],c[N*2],head[N],pick[N]; 11 int dep,p,n; 12 13 void addedge(int cu,int cv) 14 { 15 edge[p].to=cv; 16 edge[p].next=head[cu]; 17 head[cu]=p++; 18 } 19 20 void dfs(int u) 21 { 22 low[u]=++dep; 23 vis[u]=1; 24 int i; 25 for(i=head[u]; i!=-1; i=edge[i].next) 26 { 27 if(!vis[edge[i].to]) 28 dfs(edge[i].to); 29 } 30 high[u]=dep; 31 } 32 33 int lowbit(int x) 34 { 35 return x&(-x); 36 } 37 void add(int t,int v) 38 { 39 while(t<=n) 40 { 41 c[t]+=v; 42 t+=lowbit(t); 43 } 44 } 45 46 int sum(int t) 47 { 48 int res=0; 49 while(t>0) 50 { 51 res+=c[t]; 52 t-=lowbit(t); 53 } 54 return res; 55 } 56 57 int main(void) 58 { 59 int m,i,u,v; 60 memset(head,-1,sizeof(head)); 61 scanf("%d",&n); 62 for(i=1; i<n; i++) 63 { 64 scanf("%d%d",&u,&v); 65 addedge(u,v); 66 } 67 dfs(1); 68 for(i=1; i<=n; i++) 69 { 70 add(i,1); 71 pick[i]=1; 72 } 73 scanf("%d",&m); 74 while(m--) 75 { 76 getchar(); 77 char op; 78 scanf("%c%d",&op,&i); 79 if(op=='Q') 80 printf("%d ",sum(high[i])-sum(low[i]-1)); 81 else 82 { 83 if(pick[i]) 84 { 85 add(low[i],-1); 86 pick[i]=0; 87 } 88 else 89 { 90 add(low[i],1); 91 pick[i]=1; 92 } 93 } 94 } 95 return 0; 96 }