问题描述
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
问题分析与解题思路
本题难点在于如何将题目中给的苹果树转换为可利用线段树求解的问题。本题主要可分为两个步骤
- 建立苹果树，即将树枝之间的连接关系表示出来，并增加管辖范围属性
- 运用树状数组解决求和与更新问题
1. 建立苹果树
通过边的连接关系我们可以建立一棵苹果树
我们可以给苹果树的每一个节点增加一个管辖范围，代表该节点所有子树节点编号范围
管辖范围
编号为1~6的节点所管辖的范围分别就是[1,6] [2,4] [3,3] [4,4] [5,6] [6,6]，
其中左边的是左值，右边的是右值，节点1的区间是[1,6]，正好这棵子树有6个节点
上图与文字转自 http://www.cnblogs.com/gj-Acit/p/3236843.html
2. 树状数组解决求和与更新问题
由于树状数组主要解决从1开始的求和问题，而想知道每个节点以下子树（包括该节点）的苹果个数，由
以上求出的节点子树编号范围[a,b]，我们可以利用树状数组求出[1,a],[1,b]节点范围的苹果个数之和
求得[a,b]节点个数和：
节点n子树苹果个数之和 = [a,b]节点个数之和 = [1,b]节点个数之和 - [1,a-1]节点个数之和
// 由于是包括该节点的苹果个数，所以是到a-1
数据结构与算法设计极其主要代码段
对应于以上两步，我们具体阐述所用数据结构与代码段
1. 建立苹果树
（1）建立苹果树连接关系
利用vector保存边与边之间的连接关系，vector的key为当前边的左节点，value为vector，记录与该节
点相连的所有节点:
// 定义苹果树的数据结构
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）计算每个节点管辖范围[a,b],即该节点子数节点编号范围,采用深度遍历的方法求得。节点i管辖
的左边界记录在Left[i]中，右边界记录在Right[i]中
// 通过深度遍历为每个节点增加左右边界
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. 树状数组解决求和与更新问题
(1) 树状数组的求和
#define lowbit(x) (x&(-x))
// 输入i，返回[1,i]节点苹果个数之和
int sum(int i)
{
int ans = 0;
while(i>0)
{
ans += tree[i];
i -= lowbit(i);
}
return ans;
}
(2) 树状数组的更新
// 输入i，修改i节点的苹果树导致的和的变化
// 如果i节点有苹果树，则num = -1，否则num = 1
void add(int i,int num)
{
while(i<=NMAX)
{
tree[i] += num;
i += lowbit(i);
}
}
主程序中的修改代码，通过fork数组记录每个节点是否有苹果
if(fork[x]) add(Left[x],-1);
else add(Left[x],1);
fork[x] = !fork[x];
程序运行结果及分析
A. 算法复杂度
- 建立苹果树 O(e)，e为边的个数
- 递归深度遍历建立管辖范围 O(e)，因为每条边都走了两次
- 树状数组初始化 n*log（n），n为顶点个数
- 每次求和操作 log(n)
- 每次更新操作 log(n)
B. 运行时间
内存：13576kB 时间：415ms（数据来自openjudge）
心得体会与总结
- 本题的难点是想到每个给每个苹果树节点增加管辖范围属性
- 树状数组一般解决[1,i]的求和问题 [a,b] = [1,b] - [1,a] 这个等式可以方便我们计算任意区
间的和，在线段树中也有类似的应用 - 本题加深了对树状数组的理解，包括lowbit函数，求和与更新
网友评论