1 //BZOJ 1103  2 //by Cydiater  3 //2016.9.21  4 #include <iostream>  5 #include <cstdio>  6 #include <cstring>  7 #include <string>  8 #include <algorithm>  9 #include <queue> 10 #include <map> 11 #include <ctime> 12 #include <cmath> 13 #include <cstdlib> 14 #include <iomanip> 15 using namespace std; 16 #define ll unsigned int 17 #define up(i,j,n)       for(int i=j;i<=n;i++) 18 #define down(i,j,n)     for(int i=j;i>=n;i--) 19 const int MAXN=5e5+5; 20 const int oo=0x3f3f3f3f; 21 inline ll read(){ 22     char ch=getchar();ll x=0,f=1; 23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25     return x*f; 26 } 27 ll N,lable[MAXN],LINK[MAXN],len=0,siz[MAXN],son[MAXN],fa[MAXN],dep[MAXN],cnt[MAXN],Node[MAXN],top=0,tp[MAXN],t[MAXN<<2],M,x,y,k; 28 char op; 29 struct edge{ 30     int y,next; 31 }e[MAXN<<1]; 32 namespace solution{ 33     inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;} 34     void dfs1(int node,int father,int deep){ 35         fa[node]=father;dep[node]=deep;siz[node]=1;son[node]=0;int maxx=0; 36         for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=father){ 37             dfs1(e[i].y,node,deep+1); 38             siz[node]+=siz[e[i].y]; 39             if(siz[e[i].y]>maxx){ 40                 maxx=siz[e[i].y]; 41                 son[node]=e[i].y; 42             } 43         } 44     } 45     void dfs2(int node,int id){ 46         cnt[node]=++top;Node[top]=node;tp[node]=id; 47         if(son[node])dfs2(son[node],id); 48         for(int i=LINK[node];i;i=e[i].next) 49             if(e[i].y!=son[node]&&e[i].y!=fa[node]) 50                 dfs2(e[i].y,e[i].y); 51     } 52     void build(int leftt,int rightt,int root){ 53         if(leftt==rightt){ 54             t[root]=1; 55             if(leftt==1)t[root]=0; 56             return; 57         } 58         int mid=(leftt+rightt)>>1; 59         build(leftt,mid,root<<1); 60         build(mid+1,rightt,root<<1|1); 61         t[root]=t[root<<1]+t[root<<1|1]; 62     } 63     void init(){ 64         N=read(); 65         up(i,2,N){ 66             int x=read(),y=read(); 67             insert(x,y); 68             insert(y,x); 69         } 70         dfs1(1,0,1); 71         dfs2(1,1); 72         build(1,N,1); 73     } 74     void updata(int leftt,int rightt,int root){ 75         if(leftt>k||rightt<k)     return; 76         if(leftt==rightt){ 77             t[root]=0; 78             return; 79         } 80         int mid=(leftt+rightt)>>1; 81         updata(leftt,mid,root<<1); 82         updata(mid+1,rightt,root<<1|1); 83         t[root]=t[root<<1]+t[root<<1|1]; 84     } 85     int get(int leftt,int rightt,int root){ 86         if(leftt>y||rightt<x) return 0; 87         if(leftt>=x&&rightt<=y)   return t[root]; 88         int mid=(leftt+rightt)>>1; 89         return get(leftt,mid,root<<1)+get(mid+1,rightt,root<<1|1); 90     } 91     int work(int node){ 92         if(node==1)return 0; 93         int ans=0; 94         while(tp[node]!=1){ 95             x=cnt[tp[node]];y=cnt[node]; 96             ans+=get(1,N,1); 97             node=fa[tp[node]]; 98         } 99         if(node==1)return ans;100         x=cnt[tp[node]];y=cnt[node];101         ans+=get(1,N,1);102         return ans;103     }104     void slove(){105         M=read()+N-1;106         while(M--){107             scanf("%c",&op);108             if(op==‘W‘)printf("%d\n",work(read()));109             if(op==‘A‘){110                 int nodea=read(),nodeb=read();111                 if(fa[nodea]==nodeb)swap(nodea,nodeb);112                 k=cnt[nodeb];113                 updata(1,N,1);114             }115         }116     }117 }118 int main(){119     //freopen("input.in","r",stdin);120     using namespace solution;121     init();122     slove();123     return 0;124 }