這題難的不是樹(shù)狀數(shù)組(其實(shí)樹(shù)狀數(shù)組很簡(jiǎn)單)，主要是映射到樹(shù)狀數(shù)組。對(duì)樹(shù)和圖還不熟啊，導(dǎo)致這題就是借了別人的思路，可以用鄰接表建樹(shù)，
然后dfs一次就可以算出對(duì)某個(gè)節(jié)點(diǎn)它的第一個(gè)下標(biāo)(在樹(shù)狀數(shù)組中)和最后一個(gè)下標(biāo)。那個(gè)更改的時(shí)候就用這兩個(gè)下標(biāo)就行了。
比如下面的樣例
1 2
2 5
1 3
2 4
那么dfs一次之后，就會(huì)得到如下坐標(biāo)(1,5)(3,5)(2,2)(5,5)(4,4)(建圖不一樣的話(huà)，后面對(duì)應(yīng)出來(lái)的坐標(biāo)會(huì)不一樣，每一對(duì)表示樣例中的數(shù)的第一個(gè)
下標(biāo)和最后一個(gè)下標(biāo))，也就是說(shuō)從1開(kāi)始，那么第一個(gè)就是1,最后一個(gè)是5(這個(gè)5不是節(jié)點(diǎn)5,而是節(jié)點(diǎn)4，但是第5個(gè)被訪問(wèn)，其實(shí)第幾個(gè)訪問(wèn)沒(méi)關(guān)系的，
我們只是要一個(gè)區(qū)間而已，這個(gè)區(qū)間代表包含了這棵樹(shù)(或者子樹(shù))),那么和它有關(guān)的就是[1,5]，對(duì)于2這個(gè)點(diǎn)它在樹(shù)中是第3個(gè)訪問(wèn)的(第2個(gè)是節(jié)點(diǎn)3)
那么2的第一個(gè)下標(biāo)就是3,在這個(gè)子樹(shù)中最后一個(gè)訪問(wèn)的還是5,所以和它有關(guān)的區(qū)間就是[3,5].同理可以得到其他幾個(gè)點(diǎn)所對(duì)應(yīng)的坐標(biāo)，不過(guò)中間可能不
怎么好想，我是這么理解的，對(duì)每一個(gè)點(diǎn)找出影響它的所有點(diǎn)然后放在一個(gè)區(qū)間中，那么改變時(shí)就好辦了，而放在一個(gè)區(qū)間中，就可以用dfs了。
代碼如下(如果對(duì)圖理解的好的話(huà)，建議自己先寫(xiě))
CODE
1/**//*
2
ID:Klion
3 PROG:POJ_3321
4 LANG:C++
5 關(guān)鍵是映射到樹(shù)狀數(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;//似乎這個(gè)域沒(méi)用
18 Node * first;
19}Adj;
20Adj fork[100006];//鄰接表
21int tree[100006];//樹(shù)狀數(shù)組
22int low[100006],hight[100006];//對(duì)應(yīng)每一個(gè)點(diǎn)的開(kāi)始區(qū)間點(diǎn)和結(jié)束區(qū)間點(diǎn)
23//bool mark[100006];
24int cnt;//dfs用的，用來(lái)確定區(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;//開(kāi)始點(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)也就是訪問(wèn)完了這棵樹(shù)(或者子樹(shù))之后cnt的值
38 //其中沒(méi)訪問(wèn)一個(gè)點(diǎn)cnt加1
39}
40void update(int x,int val)
41{//樹(shù)狀數(shù)組的更新
42 while(x <= 100006)
43 {
44 tree[x] += val;
45 x += (x & -x);
46 }
47}
48int read(int x)
49{//樹(shù)狀數(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ù)狀數(shù)組
69 for(int i = 1;i < 100006;i++)
70 {//對(duì)每個(gè)點(diǎn)都賦值為1
71 update(i,1);
72 }
73 return ;
74}
75void get_low_hight()
76{//得到每個(gè)點(diǎn)的區(qū)間開(kāi)始點(diǎn)和區(qū)間結(jié)束點(diǎn)
77 cnt = 0;
78 //memset(mark,false,sizeof(mark));
79 dfs(1);//從根節(jié)點(diǎn)開(kāi)始
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ù)，建樹(shù)
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 /**//*這段可不要，也就是一個(gè)單向邊，那么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();//得到每個(gè)點(diǎn)的區(qū)間開(kāi)始和結(jié)束
107 init_tree();//初始化樹(shù)狀數(shù)組
108 scanf("%d%*c",&m);
109 while(m--)
110 {//m個(gè)操作
111 scanf("%s%d",&cq,&x);
112 if('Q' == cq[0])
113 {//如果是詢(xún)問(wèn)的話(huà)
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í)可以開(kāi)一個(gè)數(shù)組，這里用了先讀值然后再該，會(huì)增加一些時(shí)間
122 if(0 == ans)
123 ans = 1;//長(zhǎng)出一個(gè)蘋(píng)果
124 else
125 ans = -1;//摘掉這個(gè)蘋(píng)果
126 update(low[x],ans);//更新樹(shù)狀數(shù)組
127 }
128 }
129 return 0;
130}
131