poj 3321ツリー配列

/*
  ：
         n     ，   ，           。
    m      ：(C,i)    i        (      ，        )，
(Q,i)     i             (   i   )。
  ：
                        ，        ，
          ，               ，
                             
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100002;
int NE,n,m,cnt,c[maxn],low[maxn],high[maxn],head[maxn],vis[maxn];
struct node
{
    int u,v,next;
} Edge[maxn];
void addEdge(int u,int v)
{
    Edge[NE].u=u,Edge[NE].v=v,Edge[NE].next=head[u];
    head[u]=NE++;
}
void dfs(int u,int fa)
{
    int i,j,v;
    cnt++;
    low[u]=cnt;
    for(i=head[u]; i!=-1; i=Edge[i].next)
    {
        v=Edge[i].v;
        if(v==fa)continue;
        dfs(v,u);
    }
    high[u]=cnt;
}
int lowbit(int i)
{
    return i&(-i);
}
void add(int i,int d)
{
    while(i<=n)
    {
        c[i]+=d;
        i+=lowbit(i);
    }
}
int sum(int i)
{
    int ret=0;
    while(i)
    {
        ret+=c[i];
        i-=lowbit(i);
    }
    return ret;
}
int main()
{
    int i,j,u,v,root;
    char Q[2];
    while(scanf("%d",&n)!=EOF)
    {
        cnt=NE=0;
        memset(head,-1,sizeof(head));
        memset(c,0,sizeof(c));
        memset(vis,0,sizeof(vis));
        memset(low,0,sizeof(low));
        memset(high,0,sizeof(high));
        for(i=1; i<n; i++)
        {
            scanf("%d%d",&u,&v);
            addEdge(u,v);
        }
        dfs(1,0);
        for(i=1; i<=n; i++) add(i,1);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%s%d",&Q,&root);
            if(Q[0]=='Q') printf("%d
",sum(high[root])-sum(low[root]-1));
            else
            {
                if(!vis[low[root]])
                    add(low[root],-1);
                else add(low[root],1);
                vis[low[root]]^=1;
            }
        }
    }
    return 0;
}
/*
3
1 2
1 3
3
Q 1
C 2
Q 1
*/