• Source 
    1. /**************************************************************
    2.     Problem: 1103
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:4484 ms
    7.     Memory:9596 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. #define lowbit(x) (x&-x)
    14. //by zrt
    15. //problem:
    16. using namespace std;
    17. typedef long long ll;
    18. const double eps(1e-10);
    19. int n,m;
    20. char s[10];
    21. int H[250005],P[250005],X[250005],tot;
    22. int f[250005],l[250005];
    23. int c[500005];
    24. int tim;
    25. int stk[500005],top;
    26. void add(int pos,int x){
    27.     for(;pos<=n;pos+=lowbit(pos)){
    28.         c[pos]+=x;
    29.     }
    30. }
    31. int ask(int pos){
    32.     int ret=0;
    33.     for(;pos>0;pos-=lowbit(pos)){
    34.         ret+=c[pos];
    35.     }
    36.     return ret;
    37. }
    38. inline void Add(int x,int y){
    39.     P[++tot]=y;X[tot]=H[x];H[x]=tot;
    40. }
    41. int main(){
    42.     #ifdef LOCAL
    43.     freopen("in.txt","r",stdin);
    44.     freopen("out.txt","w",stdout);
    45.     #endif
    46.     scanf("%d",&n);
    47.     for(int i=1,x,y;i<n;i++){
    48.         scanf("%d%d",&x,&y);
    49.         if(x<y) Add(x,y);
    50.         else Add(y,x);
    51.     }
    52.     stk[top++]=1;
    53.     int k;
    54.     while(top>0){
    55.         k=stk[--top];
    56.         if(f[k]){
    57.             l[k]=++tim;
    58.             c[tim]=-1;
    59.             continue;
    60.         }else{
    61.             f[k]=++tim;
    62.             c[tim]=1;
    63.             stk[top++]=k;
    64.             for(int i=H[k];i;i=X[i]){
    65.                 stk[top++]=P[i];
    66.             }
    67.             continue;
    68.         }
    69.     }
    70.     n*=2;
    71.     for(int i=1;i<n;i++){
    72.         if(i+lowbit(i)<=n){
    73.             c[i+lowbit(i)]+=c[i];
    74.         }
    75.     }
    76.     scanf("%d",&m);
    77.     m=n/2+m-1;
    78.     for(int i=0,x,y;i<m;i++){
    79.         scanf("%s",s);
    80.         if(s[0]=='W'){
    81.             scanf("%d",&x);
    82.             printf("%d\n",ask(f[x])-1);
    83.         }else{
    84.             scanf("%d%d",&x,&y);
    85.             if(x>y){
    86.                 add(f[x],-1);
    87.                 add(l[x],1);
    88.             }else{
    89.                 add(f[y],-1);
    90.                 add(l[y],1);
    91.             }
    92.         }
    93.     }
    94.     return 0;
    95. }