这题难的不是树状数组(其实树状数组很简单)，主要是映射到树状数组。对树和图还不熟啊，导致这题就是借了别人的思路，可以用邻接表建树，
然后dfs一次就可以算出对某个节点它的第一个下标(在树状数组中)和最后一个下标。那个更改的时候就用这两个下标就行了。
比如下面的样例
1 2
2 5
1 3
2 4
那么dfs一次之后，就会得到如下坐标(1,5)(3,5)(2,2)(5,5)(4,4)(建图不一样的话，后面对应出来的坐标会不一样，每一对表示样例中的数的第一个
下标和最后一个下标)，也就是说从1开始，那么第一个就是1,最后一个是5(这个5不是节点5,而是节点4，但是第5个被访问，其实第几个访问没关系的，
我们只是要一个区间而已，这个区间代表包含了这棵树(或者子树)),那么和它有关的就是[1,5]，对于2这个点它在树中是第3个访问的(第2个是节点3)
那么2的第一个下标就是3,在这个子树中最后一个访问的还是5,所以和它有关的区间就是[3,5].同理可以得到其他几个点所对应的坐标，不过中间可能不
怎么好想，我是这么理解的，对每一个点找出影响它的所有点然后放在一个区间中，那么改变时就好办了，而放在一个区间中，就可以用dfs了。
代码如下(如果对图理解的好的话，建议自己先写)
CODE
1/**//*
2
ID:Klion
3 PROG:POJ_3321
4 LANG:C++
5 关键是映射到树状数组中
6
*/
7
#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10typedef struct node
11
{
12 int data;
13 struct node * next;
14}Node;//邻接表
15typedef struct
16{
17 int data;//似乎这个域没用
18 Node * first;
19}Adj;
20Adj fork[100006];//邻接表
21int tree[100006];//树状数组
22int low[100006],hight[100006];//对应每一个点的开始区间点和结束区间点
23//bool mark[100006];
24int cnt;//dfs用的，用来确定区间的起点和终点
25void dfs(int v)
26{//dfs 确定区间的起点和终点
27 Node * p = fork[v].first;
28 mark[v] = true;
29 ++cnt;
30 low[v] = cnt;//开始点
31 while(NULL != p)
32
{
33 //if(!mark[p->data])
34 dfs(p->data);
35 p = p->next;
36
}
37 hight[v] = cnt;//结束点也就是访问完了这棵树(或者子树)之后cnt的值
38 //其中没访问一个点cnt加1
39}
40void update(int x,int val)
41{//树状数组的更新
42 while(x <= 100006)
43 {
44 tree[x] += val;
45 x += (x & -x);
46 }
47}
48int read(int x)
49{//树状数组的求和
50 int ret = 0;
51 while(x > 0)
52 {
53 ret += tree[x];
54 x -= (x & -x);
55 }
56 return ret;
57}
58void init()
59{//初始化邻接表的其实节点
60 for(int i = 0;i < 100006;i++)
61 {
62 fork[i].data = i;
63 fork[i].first = NULL;
64 }
65 return ;
66}
67void init_tree()
68{//初始化树状数组
69 for(int i = 1;i < 100006;i++)
70 {//对每个点都赋值为1
71 update(i,1);
72 }
73 return ;
74}
75void get_low_hight()
76{//得到每个点的区间开始点和区间结束点
77 cnt = 0;
78 //memset(mark,false,sizeof(mark));
79 dfs(1);//从根节点开始
80}
81int main(void)
82{
83 freopen("3321.in","r",stdin);
84 freopen("3321.out","w",stdout);
85 int n,m;
86 int a,b;
87 int ans;
88 int x;
89 char cq[2];
90 Node * tmp;
91 init();
92 scanf("%d",&n);
93 for(int i = 1;i < n;i++)
94 {//输入数据，建树
95 tmp = new Node;
96 scanf("%d%d",&a,&b);
97 tmp->data = b;
98 tmp->next = fork[a].first;
99 fork[a].first = tmp;
100 /**//*这段可不要，也就是一个单向边，那么mark数组也可以不要了
101 tmp = new Node;
102 tmp->data = a;
103 tmp->next = fork[b].first;
104 fork[b].first = tmp;*/
105 }
106 get_low_hight();//得到每个点的区间开始和结束
107 init_tree();//初始化树状数组
108 scanf("%d%*c",&m);
109 while(m--)
110 {//m个操作
111 scanf("%s%d",&cq,&x);
112 if('Q' == cq[0])
113 {//如果是询问的话
114 ans = read(hight[x])-read(low[x]-1);//后面是low[x]-1，也就是求low[x]-hight[x]的和
115 printf("%d\n",ans);
116 }
117 else
118 {
119 //更新
120 ans = read(low[x]) - read(low[x]-1);
121 //其实可以开一个数组，这里用了先读值然后再该，会增加一些时间
122 if(0 == ans)
123 ans = 1;//长出一个苹果
124 else
125 ans = -1;//摘掉这个苹果
126 update(low[x],ans);//更新树状数组
127 }
128 }
129 return 0;
130}
131