学步园

http://acm.pku.edu.cn/JudgeOnline/problem?id=3321

#include <iostream>
using namespace std;

const int N=100001;

inline int lowbit(int x) //返回2^k,其中k是x末尾0的个数
{
 return x & (x^(x-1)); //x & (-x)
}

struct Node
{
 Node(int v=0,Node * n=NULL):vertex(v),next(n){}
 int vertex;
 Node * next;
};

Node * graph[N];

int DFSBegin[N],DFSEnd[N],depth,TreeArr[N]={0},n;
bool vst[N]={false};

int apple[N]={0};

void Modify(int pos,int d)
{
 while(pos<=n)
 {
  TreeArr[pos]+=d;
  pos+=lowbit(pos);
 }
}

int Query(int pos)
{
 int sum=0;
 while(pos>0)
 {
  sum+=TreeArr[pos];
  pos-=lowbit(pos);
 }
 return sum;
}

void DFS(int v)
{
 Node * p;
 int be=++depth;
 vst[v]=true;
 for(p=graph[v];p;p=p->next)
 {
  if(! vst[p->vertex])
   DFS(p->vertex);
 }
 DFSBegin[v]=be;
 DFSEnd[v]=depth;
}

void AddEdge(int a,int b)
{
 Node * p1=new Node(b,graph[a]);
 Node * p2=new Node(a,graph[b]);
 graph[a]=p1;
 graph[b]=p2;
}

int main()
{
 int i,a,b,t;
 char ch;
 cin>>n;
 memset(graph,0,sizeof(Node *)*n);
 depth=0;
 for(i=0;i<n-1;i++)
 {
  scanf("%d%d",&a,&b);
  AddEdge(a,b);
 }
 DFS(1);
 for(i=1;i<=n;i++)
  Modify(i,1);
 cin>>t;
 while(t--)
 {
  cin>>ch;
  scanf("%d",&a);
  if(ch=='C')
  {
   if(! apple[a])
    Modify(DFSBegin[a],-1);
   else
    Modify(DFSBegin[a],1);
   apple[a]=! apple[a];
  }
  else
   printf("%d/n",Query(DFSEnd[a])-Query(DFSBegin[a]-1));
 }
 return 0;
}