一维树状数组

Apple Tree http://poj.org/problem?id=3321

#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
const int M=100010;
struct G{
    struct E{
        int u,v,next;
    }e[M<<1];
    int le,head[M];
    void init(){
        le=0;
        mt(head,-1);
    }
    void add(int u,int v){
        e[le].u=u;
        e[le].v=v;
        e[le].next=head[u];
        head[u]=le++;
    }
}g;
struct P{
    int l,r;
}p[M];
int Clock;
void dfs(int u,int fa){
    p[u].l=++Clock;
    for(int i=g.head[u];~i;i=g.e[i].next){
        int v=g.e[i].v;
        if(v!=fa){
            dfs(v,u);
        }
    }
    p[u].r=Clock;
}
class One_Tree_Array { //一维树状数组
    typedef int typev;
    typev a[M];
public:
    void init() {
        mt(a,0);
    }
    int lowb(int t) {
        return t&(-t);
    }
    void add(int i,typev v) {
        for(; i<M; a[i]+=v,i+=lowb(i));
    }
    typev sum(int i) {
        typev s=0;
        for(; i>0; s+=a[i],i-=lowb(i));
        return s;
    }
}gx;
int now[M];
int main(){
    int n,m,u,v;
    while(~scanf("%d",&n)){
        g.init();
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&u,&v);
            g.add(u,v);
            g.add(v,u);
        }
        Clock=0;
        dfs(1,-1);
        scanf("%d",&m);
        gx.init();
        for(int i=1;i<=n;i++){
            now[i]=1;
            gx.add(i,1);
        }
        while(m--){
            char op[4];
            scanf("%s%d",op,&u);
            if(op[0]=='C'){
                gx.add(p[u].l,-now[u]);
                now[u]=-now[u];
            }
            else{
                printf("%d
",gx.sum(p[u].r)-gx.sum(p[u].l-1));
            }
        }
    }
    return 0;
}

end