#2491. 子树查询

子树查询

Description

在卡卡的房子外面有一棵苹果树,树上 有NN 个叉(编号为1N1~N ,根为11),它们通过分支连接。苹果在叉上生 长,两个苹果不会在同一个叉上生长。一个新的苹果可能会在一个空叉 上长出来,卡卡还可能会从树上摘一个苹果作为他的甜点。卡卡想了解 一棵子树上有多少苹果。

image

Format

Input

11行包含一个整数NN100,000N (N ≤100,000),表示树中叉的数 量。以下N1N -1行,每行都包含两个整数uuvv ,表示叉uu 和叉vv 通过分 支连接。下一行包含整数MM100,000M (M ≤100,000)。以下MM 行,每行都包含 一个消息,CC xx 表示改变xx 叉上的苹果状态。若叉上有苹果,则卡卡会 选择摘掉它,否则一个新的苹果在这个空叉上长大;QQ xx 表示查询xx 叉 上方子树中的苹果数量,包括xx 叉上的苹果(若存在)。注意:开始时 树上长满了苹果。

Output

对每个查询,都单行输出答案。

Samples

3
1 2
1 3
3
Q 1
C 2
Q 1
3
2

来源

POJ3321