Poj Solution 3321

http://poj.org/problem?id=3321

//* @author: 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

class cin
{
static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int leave=0;
static int nextInt() throws IOException
{
   while(leave==0)
   {
    st=new StringTokenizer(in.readLine());
    leave=st.countTokens();
   }
   leave--;
   return Integer.parseInt(st.nextToken());
}
static String nextString() throws IOException
{
   while(leave==0)
   {
    st=new StringTokenizer(in.readLine());
    leave=st.countTokens();
   }
   leave--;
   return st.nextToken();
}
static boolean hasNext() throws IOException
{
   while(leave==0)
   {
    String temp=in.readLine();
    if(temp==null)return false;
    st=new StringTokenizer(temp);
    leave=st.countTokens();
   }
   return true;
}
}

class Node //���ڽӱ�
{
int now,v=1;
Node next;
Node(int y)
{
   now=y;
   next=null;
}
}

class TreeArray //��״����
{
    int value[],n;
    int now;
    Node tree[];
    int pis[][];
    TreeArray(int num,Node e[])
    {
    n=num;
    value=new int[n+1];
    tree=e;
    pis=new int[n+1][2];
    Arrays.fill(value,0);
    }
    
    int lowBit(int t)
    {
    return t&(t^(t-1));
    }
    
    void plus(int a,int i)
    {
    while(i<=n)
    {
       value[i]+=a;
        i+=lowBit(i);
    }
    }
    
    int getSum(int i)
    {
    int sum=0;
    while(i>0)
    {
       sum+=value[i];
       i=i-lowBit(i);
    }
    return sum;
    }
    void dfs(int t) //dfs��¼ʱ��
    {
    pis[t][0]=now;
    now++;
    Node p=tree[t].next;
    while(p!=null)
    {
       dfs(p.now);
       p=p.next;
    }
    pis[t][1]=now;
    
    }
    void init()
    {
    now=0;
    dfs(1);
    for(int i=1;i<=n;i++) //��ʼ����״����
    {
       plus(1,i); 
    }
    }
}

public class Main {
    public static void main(String args[]) throws IOException
    {
    int n,t1,t2,i;
    String s;
    n=cin.nextInt();
    Node lunch[]=new Node[n+1],temp;
    for(i=1;i<=n;i++)
    {
       lunch[i]=new Node(i);
    }
    for(i=0;i< n-1;i++)
    {
       t1=cin.nextInt();
       t2=cin.nextInt();
       temp=new Node(t2);
         temp.next=lunch[t1].next;
         lunch[t1].next=temp;
    }
    TreeArray data=new TreeArray(n,lunch);
    data.init();
    n=cin.nextInt();
    for(i=0;i< n;i++)
    {
       s=cin.nextString();
       t1=cin.nextInt();
       if(s.charAt(0)=='C')
       {
        if(data.tree[t1].v==1)
        {
         data.tree[t1].v=0;
         data.plus(-1,data.pis[t1][0]+1);
        }
        else
        {
         data.tree[t1].v=1;
         data.plus(1,data.pis[t1][0]+1);
        }
       }
       else 
       {
        t2=data.getSum(data.pis[t1][0]);
        int t3=data.getSum(data.pis[t1][1]);
        System.out.println(t3-t2);
       }
    }
    }
}