問(wèn)題描述
There is an apple tree outside of kaka’s house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree.
The tree has N forks which are connected by branches. Kaka numbers the forks by 1 to N and the root is always numbered by 1. Apples will grow on the forks and two apple won’t grow on the same fork. kaka wants to know how many apples are there in a sub-tree, for his study of the produce ability of the apple tree.
The trouble is that a new apple may grow on an empty fork some time and kaka may pick an apple from the tree for his dessert. Can you help kaka?
Input
The first line contains an integer N (N ≤ 100,000) , which is the number of the forks in the tree.
The following N - 1 lines each contain two integers u and v, which means fork u and fork v are connected by a branch.
The next line contains an integer M (M ≤ 100,000).
The following M lines each contain a message which is either
“C x” which means the existence of the apple on fork x has been changed. i.e. if there is an apple on the fork, then Kaka pick it; otherwise a new apple has grown on the empty fork.
or
“Q x” which means an inquiry for the number of apples in the sub-tree above the fork x, including the apple (if exists) on the fork x
Note the tree is full of apples at the beginning
Output
For every inquiry, output the correspond answer per line.
Sample Input
3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output
3
2
問(wèn)題分析與解題思路
本題難點(diǎn)在于如何將題目中給的蘋(píng)果樹(shù)轉(zhuǎn)換為可利用線(xiàn)段樹(shù)求解的問(wèn)題山叮。本題主要可分為兩個(gè)步驟
- 建立蘋(píng)果樹(shù)逆瑞，即將樹(shù)枝之間的連接關(guān)系表示出來(lái)鲫寄，并增加管轄范圍屬性
- 運(yùn)用樹(shù)狀數(shù)組解決求和與更新問(wèn)題
1. 建立蘋(píng)果樹(shù)
通過(guò)邊的連接關(guān)系我們可以建立一棵蘋(píng)果樹(shù)
我們可以給蘋(píng)果樹(shù)的每一個(gè)節(jié)點(diǎn)增加一個(gè)管轄范圍，代表該節(jié)點(diǎn)所有子樹(shù)節(jié)點(diǎn)編號(hào)范圍
編號(hào)為1~6的節(jié)點(diǎn)所管轄的范圍分別就是[1,6] [2,4] [3,3] [4,4] [5,6] [6,6]内斯，
其中左邊的是左值，右邊的是右值，節(jié)點(diǎn)1的區(qū)間是[1,6]让腹，正好這棵子樹(shù)有6個(gè)節(jié)點(diǎn)
上圖與文字轉(zhuǎn)自 http://www.cnblogs.com/gj-Acit/p/3236843.html
2. 樹(shù)狀數(shù)組解決求和與更新問(wèn)題
由于樹(shù)狀數(shù)組主要解決從1開(kāi)始的求和問(wèn)題肾砂，而想知道每個(gè)節(jié)點(diǎn)以下子樹(shù)（包括該節(jié)點(diǎn)）的蘋(píng)果個(gè)數(shù)列赎，由
以上求出的節(jié)點(diǎn)子樹(shù)編號(hào)范圍[a,b]，我們可以利用樹(shù)狀數(shù)組求出[1,a],[1,b]節(jié)點(diǎn)范圍的蘋(píng)果個(gè)數(shù)之和
求得[a,b]節(jié)點(diǎn)個(gè)數(shù)和：
節(jié)點(diǎn)n子樹(shù)蘋(píng)果個(gè)數(shù)之和 = [a,b]節(jié)點(diǎn)個(gè)數(shù)之和 = [1,b]節(jié)點(diǎn)個(gè)數(shù)之和 - [1,a-1]節(jié)點(diǎn)個(gè)數(shù)之和
// 由于是包括該節(jié)點(diǎn)的蘋(píng)果個(gè)數(shù)镐确，所以是到a-1
數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)極其主要代碼段
對(duì)應(yīng)于以上兩步，我們具體闡述所用數(shù)據(jù)結(jié)構(gòu)與代碼段
1. 建立蘋(píng)果樹(shù)
（1）建立蘋(píng)果樹(shù)連接關(guān)系
利用vector保存邊與邊之間的連接關(guān)系源葫，vector的key為當(dāng)前邊的左節(jié)點(diǎn)诗越，value為vector息堂，記錄與該節(jié)
點(diǎn)相連的所有節(jié)點(diǎn):
// 定義蘋(píng)果樹(shù)的數(shù)據(jù)結(jié)構(gòu)
typedef vector<int> Ve;
vector<Ve>Edge(NMAX);
// 插入邊
for(int i=1; i<n; i++)
{
int u,v;
scanf("%d %d",&u,&v);
Edge[u].push_back(v);
}
（2）計(jì)算每個(gè)節(jié)點(diǎn)管轄范圍[a,b],即該節(jié)點(diǎn)子數(shù)節(jié)點(diǎn)編號(hào)范圍,采用深度遍歷的方法求得嚷狞。節(jié)點(diǎn)i管轄
的左邊界記錄在Left[i]中，右邊界記錄在Right[i]中
// 通過(guò)深度遍歷為每個(gè)節(jié)點(diǎn)增加左右邊界
void DFS(int node)
{
Left[node] = key;
for(int i=0;i < Edge[node].size(); i++)
{
key += 1;
DFS(Edge[node][i]);
}
Right[node] = key;
}
2. 樹(shù)狀數(shù)組解決求和與更新問(wèn)題
(1) 樹(shù)狀數(shù)組的求和
#define lowbit(x) (x&(-x))
// 輸入i荣堰，返回[1,i]節(jié)點(diǎn)蘋(píng)果個(gè)數(shù)之和
int sum(int i)
{
int ans = 0;
while(i>0)
{
ans += tree[i];
i -= lowbit(i);
}
return ans;
}
(2) 樹(shù)狀數(shù)組的更新
// 輸入i床未，修改i節(jié)點(diǎn)的蘋(píng)果樹(shù)導(dǎo)致的和的變化
// 如果i節(jié)點(diǎn)有蘋(píng)果樹(shù)，則num = -1振坚，否則num = 1
void add(int i,int num)
{
while(i<=NMAX)
{
tree[i] += num;
i += lowbit(i);
}
}
主程序中的修改代碼薇搁，通過(guò)fork數(shù)組記錄每個(gè)節(jié)點(diǎn)是否有蘋(píng)果
if(fork[x]) add(Left[x],-1);
else add(Left[x],1);
fork[x] = !fork[x];
程序運(yùn)行結(jié)果及分析
A. 算法復(fù)雜度
- 建立蘋(píng)果樹(shù) O(e)，e為邊的個(gè)數(shù)
- 遞歸深度遍歷建立管轄范圍 O(e)渡八，因?yàn)槊織l邊都走了兩次
- 樹(shù)狀數(shù)組初始化 n*log（n）啃洋，n為頂點(diǎn)個(gè)數(shù)
- 每次求和操作 log(n)
- 每次更新操作 log(n)
B. 運(yùn)行時(shí)間
內(nèi)存：13576kB 時(shí)間：415ms（數(shù)據(jù)來(lái)自openjudge）
心得體會(huì)與總結(jié)
- 本題的難點(diǎn)是想到每個(gè)給每個(gè)蘋(píng)果樹(shù)節(jié)點(diǎn)增加管轄范圍屬性
- 樹(shù)狀數(shù)組一般解決[1,i]的求和問(wèn)題 [a,b] = [1,b] - [1,a] 這個(gè)等式可以方便我們計(jì)算任意區(qū)
間的和，在線(xiàn)段樹(shù)中也有類(lèi)似的應(yīng)用 - 本題加深了對(duì)樹(shù)狀數(shù)組的理解呀狼，包括lowbit函數(shù)裂允，求和與更新
