poj 3321 Apple Tree

http://poj.org/problem?id=3321
テーマ:
N個の点からなる木に各点を1に初期化するには2つの操作があります
Cx:変化点の値は1から0へ0へ1へ
Q x:xをルートとするサブツリー上のポイント値の和を聞く
考え方:
主に木を木の配列にマッピングします
一度dfsは点再番号lowとhigh lowをこの点を検索したばかりの時のカウントを表し、highはそのサブツリー内のすべてのノードを検索して戻ってきたカウント番号である
例えばまたn個の点ほどルートノード1のlow=1,high=2*n
これで木の配列にマッピングされます.
コードとそのコメント:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<queue>

#include<algorithm>

#include<stack>



using namespace std;



const int N=100010;

struct node

{

    struct tt *next;

}mem[N];

struct tt

{

    struct tt *next;

    int j;

};

int n,I;//n is the number of apples I      

int c[N*2];

int high[N];

int low[N];

bool visited[N];

int apple[N];//        

void build(int i,int j)//  

{

    struct tt *t=new tt;

    t->j=j;

    t->next=mem[i].next;

    mem[i].next=t;

}

void dele()//     

{

    for(int i=1;i<=n;++i)

    mem[i].next=NULL;

}

int lowbit(int x)

{

    return x&(-x);

}

void Add(int x,int k)

{

    for(int i=x;i<=2*n;i+=lowbit(i))

    {

        c[i]+=k;

    }

}

int Sum(int x)

{

    int sum=0;

    for(int i=x;i>0;i-=lowbit(i))

    {

        sum+=c[i];

    }

    return sum;

}

void dfs(int x)//     

{

    visited[x]=true;

    ++I;

    low[x]=I;

    struct tt *t=new tt;

    t=mem[x].next;

    while(t!=NULL)

    {

        if(visited[t->j]==false)

        {

            dfs(t->j);

        }

        t=t->next;

    }

    ++I;

    high[x]=I;



}

int main()

{

   int m;

   while(scanf("%d",&n)!=EOF)

   {

       memset(c,0,sizeof(c));

       for(int i=1;i<n;++i)

       {

           int l,r;

           scanf("%d %d",&l,&r);

           build(l,r);

           build(r,l);

       }

       I=0;

       memset(visited,false,sizeof(visited));

       dfs(1);

       for(int i=1;i<=n;++i)

       {

           apple[i]=1;

       }

       for(int i=1;i<=2*n;++i)

       {

           Add(i,1);//       

       }

       scanf("%d",&m);

       while(m--)

       {

           char c;

           int k;

           getchar();

           scanf("%c %d",&c,&k);

           if(c=='Q')

           {

               printf("%d
",(Sum(high[k])-Sum(low[k]-1))/2);

           }else

           {

               if(apple[k]==1)

               {

                   apple[k]=0;

                   Add(low[k],-1);

                   Add(high[k],-1);

               }

               else

               {

                   apple[k]=1;

                   Add(low[k],1);

                   Add(high[k],1);

               }

           }

       }

       dele();

   }

   return 0;

}