Fork me on GitHub

POJ3321--Apple Tree

Posted on | In |
Words count in article: 1.1k 字 | Reading time ≈ 5 mins

题目：

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?

img

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

1
2
3
4
5
6
7
3
1 2
1 3
3
Q 1
C 2
Q 1

Sample output

1
2
3
2

解析

题意：有一颗苹果树，一开始每个节点都有一个苹果，之后有俩种操作：1）摘下一个苹果或者在空结点长出一个新苹果；2）查询以x为根节点的子树的权值和。

第一个操作就是该节点的权值发生改变：1🠖0：摘下一个苹果；0🠖1：长出新苹果；

第二操作就是求一个权值和。

因为这个苹果树变化较频繁而且要求权值和，用遍历不是很好，所以引入树状数组$c[]$，以访问时间为顺序，在后后续遍历过程中以时间的形式变为线性结构。

1.设：

​ $d[u]$为节点的初始访问时间

​ $f[u]$为节点的结束访问时间（从它的子树回溯回来的时间）

$[d[u],f[u]]$就是以$u$为根的子树的结构，若$[d[v],f[v]]$是$[d[u],f[u]]$的子区间，则以$u$为根节点的树包含了以$v$为根节点的子树。在代码中用DFS来计算这个区间

2.若为第一个操作即 $C x$,也就是节点的权值发生变化，则$a[f[x]]=(a[f[x]]+1)\%2$,并从$c[f[x]]$出发调整树状数组$c[]$。在代码中用change

3.若为第二个操作即$Qx$，则以节点x为根节点的权值和为$sum(f[x])-sum(d[x]-1)$,其中$sum[x]$为前$x$个访问时间的前缀和。

完整代码

F3B5DBD966FD2D14614139CCDA76D4DC.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstring>
#define MAX 100002
using namespace std;

struct node1 
{
	int tail, next;
}edge[MAX];

struct  node2 
{
	int r, l;
}apple[MAX];

int s[MAX], cnt, c[MAX], a[MAX];  //后序遍历序号为cnt，权值为a[i]，树状数组为c，结点i相连的第i条边为s[i]

void DFS(int u){  //求区间
	int i;
	apple[u].l = cnt;
	for(i = s[u]; i != -1; i = edge[i].next){
		DFS(edge[i].tail);
	}
	apple[u].r = cnt ++;
}

inline int lowbit(int x){
	return x & (-x);
}

void change (int x){  //从a[x]出发，调整树状数组
	int i;
	if(a[x]){   //如果这个元素非零，那就是长出了新苹果
		for(i = x; i < cnt; i += lowbit(i)){
			c[i] ++;
		}
	}
	else {  //该点的苹果被摘下来
		for(i = x; i < cnt; i += lowbit(i)){
			c[i] --;
		}
	}
}

int sum(int x){  //求前x个点的权值和
	int i, res = 0;
	for(i = x; i > 0; i -= lowbit(i)){
		res += c[i];
	}
	return res;
}

int main(){
	int i, m, n, t1, t2, t;
	char str[3];
	scanf("%d", &n); //树的节点
	memset(s, -1, sizeof(s[0]) * (n+1));
	memset(c, 0, sizeof(c[0]) * (n+1));
	memset(apple, 0, sizeof(apple[0]) * (n+1));
	for(int i = 0; i < n - 1; i ++){
		scanf("%d %d", &t1, &t2);
		edge[i].tail = t2;
		edge[i].next = s[t1]; 
		s[t1] = i;   //结点t1链接边序号i
	}
	cnt = 1;
	DFS(1);
	scanf("%d", &m);  //信息的条数
	for(i = 1; i <= n; i ++){  //构造树状数组c
		a[i] = 1;
		change(i);
	}
	while(m --){
		scanf("%s %d", &str, &t);  //命令标志（Q，C）str和结点序号t
		if(str[0] == 'Q'){
			printf ("%d\n", sum(apple[t].r) - sum(apple[t].l-1));
		}
		else {
			a[apple[t].r] = (a[apple[t].r] + 1) % 2;   //t结点上的权重变
			change(apple[t].r);
		}
	}
	return 0;
}
0%