zoj 3686簡単な線分の木は更新して久しくこの東を書いていません!!!

/*
線分の木のような感じで、最初はあまり良い考えがなく、ネット上の変換方法を覗いてみました!
テーマ:
1本の木にはn個のノード(1<=N<=10000000)があり、ルートは1であり、各ノードにはラベルがあり、初期値は0である.
現在2種類の操作があります
o操作:(o,x)ノードxおよびそのすべての子孫ノードのラベル値を逆(および1異または)にします.
q操作:(q,x)ノードxとその子孫ノードのラベル値が1の個数を出力する.
操作回数はm回(1<=M<=10000)である.
テーマ構想:
ルートから各ノードを順次巡回し、各ノードを巡回順に再番号付けする(beg).
このようにして,再番号付けされたノード,ルートおよびその接続されたサブツリーのノードを連続させることができ,これにより,区間更新と区間問合せを操作することができる.
あるサブツリーの最大のノード番号(end)を巡回時に記録し、あるノードとそのサブツリーの範囲、すなわち
[ beg[x] , end[x] ].
*/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int maxn=100002;
int beg[maxn],end[maxn],head[maxn],sum[maxn<<2],col[maxn<<2];
int NE=0,n,m,tot;
char op[2];
struct node
{
    int u,v,next;
}Edge[maxn<<2];
void addEdge(int u,int v)
{
    Edge[NE].u=u,Edge[NE].v=v,Edge[NE].next=head[u];
    head[u]=NE++;
}
int dfs(int rt)
{
    beg[rt]=++tot;
    for(int i=head[rt];i!=-1;i=Edge[i].next)dfs(Edge[i].v);
    end[rt]=tot;
}
void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r)
{
    col[rt]=sum[rt]=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
   // PushUp(rt);
}
void PushDown(int rt,int l,int r)
{
    if(col[rt]!=0)
    {
        int mid=(l+r)>>1;
        col[rt<<1]^=col[rt];
        col[rt<<1|1]^=col[rt];
        sum[rt<<1]=mid-l+1-sum[rt<<1];
        sum[rt<<1|1]=r-mid-sum[rt<<1|1];
        col[rt]=0;
    }
}
void update(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        col[rt]^=1;
        sum[rt]=r-l+1-sum[rt];
        return;
    }
    PushDown(rt,l,r);
    int mid=(l+r)>>1;
    if(mid>=L)update(lson,L,R);
    if(mid<R)update(rson,L,R);
    PushUp(rt);
}
int query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return sum[rt];
    PushDown(rt,l,r);
    int mid=(l+r)>>1;
    int res=0;
    if(mid>=L)res+=query(lson,L,R);
    if(mid<R)res+=query(rson,L,R);
    return res;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        NE=tot=0;
        int i,j,u,v;
        memset(head,-1,sizeof(head));
        for(v=2;v<=n;v++)
        {
            cin>>u;
            addEdge(u,v);
        }
        dfs(1);
        build(1,1,n);
        while(m--)
        {
            cin>>op>>u;
            if(op[0]=='o')update(1,1,n,beg[u],end[u]);
            else printf("%d
",query(1,1,n,beg[u],end[u]));
        }
        puts("");
    }
    return 0;
}