這題難的不是樹狀數組(其實樹狀數組很簡單)，主要是映射到樹狀數組。對樹和圖還不熟啊，導致這題就是借了別人的思路，可以用鄰接表建樹，
然后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