记录编号	600953	评测结果	RRRRRRRRRR
题目名称	1.加法问题	最终得分	0
用户昵称	ChenBp	是否通过	未通过
代码语言	C++	运行时间	1.429 s
提交时间	2025-05-21 21:49:09	内存使用	3.33 MiB

// http://poj.org/problem?id=3321
#include <iostream>
using namespace std;
const int N=1e5+5;
int n,m;

int head[N],nxt[N],to[N],num=0;
void adde(int u,int v){
    num++;
    to[num]=v;
    nxt[num]=head[u];
    head[u]=num;
}

int dx[2*N],l=0,s[N],e[N];
void dfs(int x,int fa){
    dx[++l]=x;
    s[x]=l;
    for(int i=head[x];i;i=nxt[i]){
        int v=to[i];
        if(v==fa) continue;
        dfs(v,x);
    }
    dx[++l]=x;
    e[x]=l;
}

int a[2*N],f[2*N];
int lowbit(int x){
    return x&(-x);
}
int ask(int x){
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=f[x];
    return ans;
}
void add(int x,int y){
    for(;x<=n;x+=lowbit(x)){
        f[x]+=y;
    }
}

int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adde(u,v);
    }
    dfs(1,0);
//    for(int i=1;i<=n;i++) cout<<s[i]<<" "<<e[i]<<endl;
    for(int i=1;i<=n*2;i++){
        a[i]=1;
        add(i,1);
    }
    
    cin>>m;
    while(m--){
        char c;
        int x;
        cin>>c>>x;
        if(c=='C'){
            if(a[x]){
                a[x]=0;
                add(s[x],-1);
                add(e[x],-1);
            }else{
                a[x]=1;
                add(s[x],1);
                add(e[x],1);
            }
        }else{
            cout<<(ask(e[x])-ask(s[x]-1))/2<<endl;
        }
    }
    return 0;
}