poj 3321 Apple Tree

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 using namespace std;
  5 const int maxn=100000+5;
  6 struct edge
  7 {
  8     int v;
  9     edge *next;
 10 };
 11 edge *g[maxn];
 12 edge mall[2*maxn];
 13 edge *tmp;
 14 int c[maxn];
 15 int s[maxn];
 16 int e[maxn];
 17 int vis[maxn];
 18 int cnt;
 19 int n;
 20 int top;
 21 void addedge(int u,int v)
 22 {
 23         tmp=&mall[top++];
 24         tmp->v=v;
 25         tmp->next=g[u];
 26         g[u]=tmp;
 27 }
 28 void dfs(int u)
 29 {
 30     vis[u]=1;
 31     s[u]=++cnt;
 32     for(edge *p=g[u];p!=NULL;p=p->next)
 33     {
 34         int v=p->v;
 35         if(!vis[v])
 36             dfs(v);
 37     }
 38     e[u]=cnt;
 39 }
 40 int lowbit(int x)
 41 {
 42     return x&-x;
 43 }
 44 int sum(int x)
 45 {
 46     int ret=0;
 47     while(x>0)
 48     {
 49         ret+=c[x];
 50         x-=lowbit(x);
 51     }
 52     return ret;
 53 }
 54 void add(int x,int inc)
 55 {
 56     while(x<=n)
 57     {
 58         c[x]+=inc;
 59         x+=lowbit(x);
 60     }
 61 }
 62 int main()
 63 {
 64     while(scanf("%d",&n)!=EOF)
 65     {
 66         int u,v;
 67         memset(g,0,sizeof(g));
 68         top=0;
 69         for(int i=1;i<n;i++)
 70         {
 71             scanf("%d%d",&u,&v);
 72             addedge(u,v);
 73             addedge(v,u);
 74         }
 75         cnt=0;
 76         memset(vis,0,sizeof(vis));
 77         dfs(1);
 78         int m;
 79         scanf("%d",&m);
 80         char com[5];
 81         int x;
 82         memset(c,0,sizeof(c));
 83         for(int i=1;i<=n;i++)
 84             add(i,1);
 85         for(int i=0;i<m;i++)
 86         {
 87             scanf("%s%d",com,&x);
 88             if(com[0]=='Q')
 89                 printf("%d
",sum(e[x])-sum(s[x]-1));
 90             else
 91             {
 92                 if(sum(s[x])-sum(s[x]-1)==0)
 93                     add(s[x],1);
 94                 else
 95                     add(s[x],-1);
 96             }
 97         }
 98     }
 99     return 0;
100 }