這題難的不是樹狀數(shù)組(其實(shí)樹狀數(shù)組很簡單)，主要是映射到樹狀數(shù)組。對樹和圖還不熟啊，導(dǎo)致這題就是借了別人的思路，可以用鄰接表建樹，
然后dfs一次就可以算出對某個節(jié)點(diǎn)它的第一個下標(biāo)(在樹狀數(shù)組中)和最后一個下標(biāo)。那個更改的時候就用這兩個下標(biāo)就行了。
比如下面的樣例
1 2
2 5
1 3
2 4
那么dfs一次之后，就會得到如下坐標(biāo)(1,5)(3,5)(2,2)(5,5)(4,4)(建圖不一樣的話，后面對應(yīng)出來的坐標(biāo)會不一樣，每一對表示樣例中的數(shù)的第一個
下標(biāo)和最后一個下標(biāo))，也就是說從1開始，那么第一個就是1,最后一個是5(這個5不是節(jié)點(diǎn)5,而是節(jié)點(diǎn)4，但是第5個被訪問，其實(shí)第幾個訪問沒關(guān)系的，
我們只是要一個區(qū)間而已，這個區(qū)間代表包含了這棵樹(或者子樹)),那么和它有關(guān)的就是[1,5]，對于2這個點(diǎn)它在樹中是第3個訪問的(第2個是節(jié)點(diǎn)3)
那么2的第一個下標(biāo)就是3,在這個子樹中最后一個訪問的還是5,所以和它有關(guān)的區(qū)間就是[3,5].同理可以得到其他幾個點(diǎn)所對應(yīng)的坐標(biāo)，不過中間可能不
怎么好想，我是這么理解的，對每一個點(diǎn)找出影響它的所有點(diǎn)然后放在一個區(qū)間中，那么改變時就好辦了，而放在一個區(qū)間中，就可以用dfs了。
代碼如下(如果對圖理解的好的話，建議自己先寫)
CODE
1/**//*
2
ID:Klion
3 PROG:POJ_3321
4 LANG:C++
5 關(guān)鍵是映射到樹狀數(shù)組中
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];//樹狀數(shù)組
22int low[100006],hight[100006];//對應(yīng)每一個點(diǎn)的開始區(qū)間點(diǎn)和結(jié)束區(qū)間點(diǎn)
23//bool mark[100006];
24int cnt;//dfs用的，用來確定區(qū)間的起點(diǎn)和終點(diǎn)
25void dfs(int v)
26{//dfs 確定區(qū)間的起點(diǎn)和終點(diǎn)
27 Node * p = fork[v].first;
28 mark[v] = true;
29 ++cnt;
30 low[v] = cnt;//開始點(diǎn)
31 while(NULL != p)
32
{
33 //if(!mark[p->data])
34 dfs(p->data);
35 p = p->next;
36
}
37 hight[v] = cnt;//結(jié)束點(diǎn)也就是訪問完了這棵樹(或者子樹)之后cnt的值
38 //其中沒訪問一個點(diǎn)cnt加1
39}
40void update(int x,int val)
41{//樹狀數(shù)組的更新
42 while(x <= 100006)
43 {
44 tree[x] += val;
45 x += (x & -x);
46 }
47}
48int read(int x)
49{//樹狀數(shù)組的求和
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{//初始化鄰接表的其實(shí)節(jié)點(diǎn)
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{//初始化樹狀數(shù)組
69 for(int i = 1;i < 100006;i++)
70 {//對每個點(diǎn)都賦值為1
71 update(i,1);
72 }
73 return ;
74}
75void get_low_hight()
76{//得到每個點(diǎn)的區(qū)間開始點(diǎn)和區(qū)間結(jié)束點(diǎn)
77 cnt = 0;
78 //memset(mark,false,sizeof(mark));
79 dfs(1);//從根節(jié)點(diǎn)開始
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 {//輸入數(shù)據(jù)，建樹
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數(shù)組也可以不要了
101 tmp = new Node;
102 tmp->data = a;
103 tmp->next = fork[b].first;
104 fork[b].first = tmp;*/
105 }
106 get_low_hight();//得到每個點(diǎn)的區(qū)間開始和結(jié)束
107 init_tree();//初始化樹狀數(shù)組
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 //其實(shí)可以開一個數(shù)組，這里用了先讀值然后再該，會增加一些時間
122 if(0 == ans)
123 ans = 1;//長出一個蘋果
124 else
125 ans = -1;//摘掉這個蘋果
126 update(low[x],ans);//更新樹狀數(shù)組
127 }
128 }
129 return 0;
130}
131