A Simple Tree Problem

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4969

询问次数那么多，本能想到线段树。对区间重标号，区间询问， 更新。

int N,M,K, len;
int ll[MM<<2], rr[MM<<2];
int ff[MM<<2];
int sum[MM<<2];
vector<int>edge[MM];

void dfs(int u) {
    int i,j,k,v;
    ll[u]=len++;
    for(i=0;i<edge[u].size();i++) {
        v=edge[u][i];
        dfs(v);
    }
    rr[u]=len-1;
}
void get_data() {
    int i,j,k,a;
    len=1;
    for(i=0;i<MM;i++) edge[i].clear();
    forn(i,2,N)    {
        scanf("%d",&a);
        edge[a].push_back(i);
    }
    dfs(1);
}
void push_down(int l,int r,int rt) {
    if(ff[rt]) {
        int mid=(l+r)>>1;
        ff[lson]^=1; ff[rson]^=1;
        ff[rt]=0;
        sum[lson]=(mid-l+1)-sum[lson];
        sum[rson]=(r-mid)-sum[rson];
    }
}
void push_up(int rt) {
    sum[rt]=sum[lson]+sum[rson];
}
void update(int L,int R,int l,int r,int rt) {
    if(L<=l && r<=R) {
        sum[rt]=(r-l+1)-sum[rt]; ff[rt]^=1;
        return;
    }
    int mid=(l+r)>>1;
    push_down(l,r,rt);
    if(L<=mid) update(L,R,l,mid,lson);
    if(R>mid)  update(L,R,mid+1,r,rson);
    push_up(rt);
}
int query(int L,int R,int l,int r,int rt) {
    if(L<=l && r<=R) {
        return sum[rt];
    }
    push_down(l,r,rt);
    int mid=(l+r)>>1, ret=0;
    if(L<=mid) ret+=query(L,R,l,mid,lson);
    if(R>mid)  ret+=query(L,R,mid+1,r,rson);
    push_up(rt);
    return ret;
}
void solve() {
    int i,j,k,a,l,r;
    char op;
    for(i=0;i<(MM<<2);i++) ff[i]=sum[i]=0;
    while(M--) {
        getchar();
        scanf("%c%d",&op,&a);
        if(op=='o') {
            update(ll[a],rr[a],1,len-1,1);
        }
        else {
            printf("%d\n",query(ll[a],rr[a],1,len-1,1));
        }
    }
    printf("\n"); 
}