/* 很容易发现这题用线段树来做 树形结构稍微处理一下就可以变为线性结构，dfs跑一遍将树中的结点重新编号，对于每个节点，当访问完子树之后，将子树的最大节点也保存，这样就能得到一个区间段，于是乎，每棵子树的编号就都变成连续的（读入时的标号与线段树中实际标号不一样，所以先用一个pre数组来记录原来的标号），剩下的就可以套用线段树或者是树状数组的模板了，当查询某个结点时查询所对应的连续区间就可以了 */ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define maxn 100010 struct node{ int lef, rig, id; }tree[maxn]; int root[maxn]; int n, q, v; struct E{ int v, next; }edge[maxn]; int pre[maxn], apple[maxn]; struct SEG{ int lef, rig, mid, ans; }seg[maxn*4]; void dfs(int pp) { tree[pp].lef = v; for(int i= pre[pp]; i!= -1; i= edge[i].next) dfs(edge[i].v); root[pp] = v; tree[pp].rig = v++; } void maketree(int num, int lef, int rig) { seg[num].lef = lef; seg[num].rig = rig; seg[num].mid = (lef + rig) >> 1; seg[num].ans = rig - lef + 1; if( lef != rig) { maketree(num*2, lef, seg[num].mid); maketree(num*2+1, seg[num].mid+1, rig); } } int cal( int num, int lef, int rig) { if( seg[num].lef == lef && seg[num].rig == rig) return seg[num].ans; if( rig <= seg[num].mid) return cal( num*2, lef, rig); else if( lef > seg[num].mid) return cal( num*2+1 , lef, rig); else return cal( num*2, lef , seg[num].mid) + cal(num*2+1, seg[num].mid+1, rig); } void insert( int num, int lef, int val) { seg[num].ans += val; if( seg[num].lef == seg[num].rig) return; if( lef <= seg[num].mid) insert( num*2, lef, val); else if( lef > seg[num].mid) insert( num*2+1, lef, val); } void init() { int aa, bb, value = 0; memset( pre, -1, sizeof(pre)); for(int i= 1; i<n; i++) { scanf("%d%d", &aa, &bb); edge[value].v = bb; edge[value].next = pre[aa]; pre[aa] = value++; } for(int i= 1; i<= n; i++) apple[i] = 1; } int main() { int aa, bb; char tmp[10]; scanf("%d", &n); init(); v = 1; dfs(1); maketree(1, 1, n); scanf("%d", &q); for(int i= 0; i<q; i++) { scanf("%s%d", tmp, &aa); if( tmp[0] == 'Q') printf("%d ", cal(1, tree[aa].lef, tree[aa].rig)); else { if( apple[root[aa]] == 1) bb = -1; else bb = 1; insert( 1, root[aa], bb); apple[root[aa]] = 1 - apple[root[aa]]; } } return 0; }