Apple Tree(ツリー配列＋dfs順＋隣接テーブル配列(チェーン式順星)

リンク:http://poj.org/problem?id=3321
Description
The e is an apple tree outside of ka's house.Every autumn,a lot of apples will grow in the tree.ka likes apple very much,so he has been carefully nurturing the big apple.
The tree has N forks which are connected byBbrancchs.Kakanumbes the forks by 1 to N and the root is always numbeed by 1.Apples will grow on the forks and tappple won'growowon the same the same foratttttttttttttttttttthethethe the thethethethethethe attttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttee.
The trouble is that a new apple may grow on an empty fork some time and ka may pick an apple from the tree for his dessert.Can you help ka?
 

 
Input
The first line contains an integer N(N≦100,000)、which is the number of the forks in the forks in the tree.The follwing N-1 lins each contatainintegers u and v、which means fork and and fork and fork and fork fork forfork v.ininininininintttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt「C x」which means the existence of the apple on fork x has been changed.i.e.if there is an apple on the fork,then Kaka pick it;otherswise a new apple has grown the empty fork.or「Q x」which means an inquiry for the number of appes the sub-tree above the fork x,including the apple(if exists)on the fork Note the Fregies apple of
Output
For everry inquiry,output the corempend answer per line.
Sample Input

3
1 2
1 3
3
Q 1
C 2
Q 1

Sample Output

3
2

 
一つの木にリンゴが生えています.各枝のノードにはリンゴが長くないという二つの状態があります.一つの操作は木の枝の上のリンゴの状態を変えることができます.
 
考え方:dfs順序では、サブツリーは連続区間にある.この問題は修正して区間で調べます.ツリー配列を変換して処理します.
 
コード:

#include
using namespace std;
const int maxn=210100;
struct node
{
    int to;
    int next;
}e[maxn];
char s;int x;
int in[maxn],out[maxn],c[maxn],cnt;
int n,m,tot,head[maxn],vis[maxn];
void add_edge(int u,int v)
{
    tot++;
    e[tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;
}
int lowbit(int x)
{
    return x&(-x);
}
void dfs(int x)
{
    in[x]=++cnt;
    for(int i=head[x];i;i=e[i].next)
    dfs(e[i].to);
    out[x]=cnt;
}
void update(int x,int add)
{
    while(x<=n)
    {
        c[x]+=add;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int s=0;
    while(x>0)
    {
        s+=c[x];
        x-=lowbit(x);
    }
    return s;
}
int main()
{
    int a,b;
    cin>>n;
    for(int i=1;i>a>>b;
        add_edge(a,b);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    update(in[i],1),vis[i]=1;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>s>>x;
        if(s=='C')
        {
            if(vis[x])update(in[x],-1);
            else update(in[x],1);
            vis[x]=1-vis[x];
        }
        if(s=='Q')
        cout<