(利用树状数组统计子树权和8.3.1)POJ 3321 Apple Tree(利用树状数组动态统计子树权和)

/* 
 * POJ_3321.cpp 
 * 
 *  Created on: 2013年11月5日 
 *      Author: Administrator 
 */  
  
#include   
#include   
#include   
  
using namespace std;  
  
const int maxn = 100010;  
  
struct node1{  
    int next;//下一条边的序号为edge[i].next  
    int tail;//与dii条边相连的节点为edge[i].tail  
}edge[maxn];  
  
struct node2{//第i个节点为根的子树在后根序列中的区间为[apple[i].l,apple[i].r];  
    int l;  
    int r;  
}apple[maxn];  
  
/** 
 * a[i]: 第ige节点的权值 
 * cnt: 后跟序列中的序号 
 * s[i]: 第i条边的序号 
 * c[]: 树状数组 
 */  
int a[maxn],cnt,s[maxn],c[maxn];  
  
void DFS(int u){//从节点u出发计算以每个节点为根节点的子树区间[apple[i].l,apple[i].r]  
    apple[u].l = cnt;  
  
    int i;  
    for(i = s[u]; i != -1 ; i = edge[i].next){  
        DFS(edge[i].tail);  
    }  
    apple[u].r = cnt++;  
}  
  
int lowbit(int x){  
    return x&(-x);  
}  
  
void change(int x){//从a[x]出发调整树状数组  
    int i;  
    if(a[x]){  
        for(i = x ; i < cnt ; i += lowbit(i)){  
            c[i]++;  
        }  
    }else{  
        for(i = x ; i < cnt ; i += lowbit(i)){  
            c[i]--;  
        }  
    }  
}  
  
int sum(int x){//计算a[1]....a[k]的和  
    int i;  
    int res = 0;  
    for(i = x ; i >





 0 ; i -= lowbit(i)){  
        res += c[i];  
    }  
  
    return res;  
}  
  
int main(){  
    int i,n,m,t1,t2,t;  
    char str[3];  
    scanf("%d",&n);  
    memset(s,-1,sizeof(s[0])*(n+1));  
    memset(c,0,sizeof(c[0])*(n+1));  
    memset(apple,0,sizeof(apple[0])*(n+1));  
    for(i = 0 ; i < n-1 ; ++i){  
        scanf("%d%d",&t1,&t2);  
        edge[i].tail = t2;  
        edge[i].next = s[t1];  
        s[t1] = i;  
    }  
  
    cnt = 1;  
    DFS(1);  
  
    scanf("%d",&m);  
    for(i = 1 ; i <= n ; ++i){  
        a[i] = 1;  
        change(i);  
    }  
  
    while(m--){  
        scanf("%s%d",str,&t);  
        if(str[0] == 'Q'){  
            printf("%d\n",sum(apple[t].r) - sum(apple[t].l - 1));  
        }else{  
            a[apple[t].r] = (a[apple[t].r] + 1)%2;  
            change(apple[t].r);  
        }  
    }  
  
    return 0;  
}