POJ 3321 Apple Tree 树状数组

题意：有一棵树，树上有一些叉，每个叉上刚开始都有一个苹果，对每个叉可以有两种操作，若刚开始有苹果，则变为没苹果，若刚开始没苹果，则变为有一个苹果。有多次操作，有多次询问，对于每次询问，回答该结点以及该结点以上有多少个苹果。
思路：树状数组的好题。首先可以dfs树，为每个结点映射一个区间，然后就是树状数组的裸题了。树状数组不仅可以应用在普通题目上，而且可以自己构造区间。
代码：
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <string.h> 
#include <algorithm> 
using namespace std; 
 
const int N = 100010; 
int up[N],down[N],head[N],order,n,numedge,num[N],dit[N]; 
struct edge{ 
    int lp,rp,next; 
}ee[N * 2]; 
void init(){ 
    order = 1; 
    numedge = 0; 
    memset(up,0,sizeof(up)); 
    memset(down,0,sizeof(down)); 
    memset(head,-1,sizeof(head)); 
    for(int i = 1; i <= N - 10; ++i) 
        num[i] = ( i & (-i) ); 
} 
void add_edge(int x,int y){ 
    ee[numedge].lp = x; 
    ee[numedge].rp = y; 
    ee[numedge].next = head[x]; 
    head[x] = numedge++; 
} 
void dfs(int x){ 
    down[x] = order; 
    for(int i = head[x]; i != -1; i = ee[i].next){ 
       int y = ee[i].rp; 
       dfs(y); 
    } 
    up[x] = order++; 
} 
int lowbit(int x){ 
    return x & (-x); 
} 
int sum(int x){ 
    int s = 0; 
    while(x > 0){ 
       s += num[x]; 
       x -= lowbit(x); 
    } 
    return s; 
} 
void update(int x,int add){ 
    while(x < N){ 
       num[x] += add; 
       x += lowbit(x); 
    } 
} 
int main(){ 
    scanf("%d",&n); 
       init(); 
       int x,y; 
       for(int i = 1; i < n; ++i){ 
          scanf("%d%d",&x,&y); 
          dit[x] = dit[y] = 1; 
          add_edge(x,y); 
       } 
       dfs(1); 
       int m; 
       scanf("%d",&m); 
       char ss[3]; 
       while(m--){ 
         scanf("%s%d",ss,&x); 
         if(ss[0] == 'Q'){ 
           printf("%d\n",sum(up[x]) - sum(down[x] - 1)); 
         } 
         else{ 
             if(dit[x]) 
                update(up[x],-1); 
             else 
                 update(up[x],1); 
             dit[x] = !dit[x]; 
         } 
       } 
    return 0; 
} 

补充：软件开发 , C++ ,