poj 3321

给出一棵树，判断 以 某个 节点 为 根 的子树 有多少个节点有苹果。。

知道要用树状数组求和，但是 每个子树节点编号不连续，头疼，后来看了一些大神的报告才 恍然大悟。

可以先进行一次 dfs 后序遍历，对 每个节点重新编号，使子树的每个节点编号连续，并且根节点编号最大，同时要记录每棵子树的范围

即 子树 的最大编号和最小编号，然后 树状数组。。

ps：建树也不太会。。

[cpp] 
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
 
#define MAXN 100005 
 
struct Edge{ 
    int v,next;//v记录边头部，next记录下一边 
}edge[MAXN]; 
 
struct Range{//存每个子树范围 
    int low,high; 
}range[MAXN]; 
 
int root[MAXN];// root[u]以u为根的节点编号 
int c[MAXN]; 
int app[MAXN];//the state of point 
int index,n,m; 
 
inline void addEdge(int u,int v){//加边，将节点插入头部 
    edge[index].v=v; 
    edge[index].next=root[u]; 
    root[u]=index++; 
} 
 
inline void dfs(int u){//后序遍历 
    range[u].low=index;//记录最小编号 
    if(root[u]==-1){ 
        range[u].high=index++; 
        return; 
    } 
    else { 
        for(int i=root[u];i!=-1;i=edge[i].next){ 
            dfs(edge[i].v); 
        } 
    } 
    range[u].high=index++;//记录最大编号，即根的编号 
} 
 
inline int lowbit(int x){ 
    return x&(-x); 
} 
 
inline void update(int i,int v){ 
    while(i<=n){ 
        c[i]+=v; 
        i+=lowbit(i); 
    } 
} 
 
inline int getsum(int i){ 
    int sum=0; 
    while(i>0){ 
        sum+=c[i]; 
        i-=lowbit(i); 
    } 
    return sum; 
} 
 
int main(){ 
    int i,j; 
    int u,v; 
    char cmd; 
    while(scanf("%d",&n)==1){ 
        memset(root,-1,sizeof(root)); 
        index=1; 
        for(i=1;i<n;i++){ 
            scanf("%d%d",&u,&v); 
            addEdge(u,v); 
        } 
        fill(app,app+n+5,1); 
        for(i=1;i<=n;i++)c[i]=lowbit(i);//初始化，一开始每个节点都有 apple 
        index=1; 
        dfs(1); 
        scanf("%d",&m); 
        while(m--){ 
            scanf(" %c%d",&cmd,&u); 
            if(cmd=='C'){ 
                int val=1; 
                if(app[u])val=-1; 
                app[u]=!app[u]; 
                update(range[u].high,val); 
            } 
            else { 
                int val=getsum(range[u].high)-getsum(range[u].low-1); 
                printf("%d/n",val); 
            } 
        } 
    } 
    return 0; 
} 
 
/*
10
1 5 3
3 2
1 3
5 7
10 9
10 8
5 10
5 6
100
Q 1
10
Q 2
1
C 10
Q 1
9
Q 10
2
C 10
Q 10
3
*/ 

 作者：qingniaofy