Fork me on GitHub

POJ 3321 DFS序 + 树状数组 查询子树

题目:传送门

题意:

给一个树,查询结点下的子树的苹果总数,并且要求支持增减苹果

题解:

查询子树,我们首先想到的是DFS序,还要支持修改操作,我们可以用树状数组维护这个DFS序,因为还要查询,所以我在实际程序中使用了欧拉序。

AC代码:

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
#include <iostream>
#include <vector>
#include <cstdio>
#define debug(x) cout<<#x<<" = "<<x<<endl;
#define INF 0x3f3f3f3f
using namespace std;

const int maxn = 100010;
vector<vector<int> > g(maxn);
//vector<int> g[maxn]这么写会TLE 虽让我也不知道为什么
int step, start_dfs[maxn], end_dfs[maxn], f[maxn];

void dfs(int u) {
start_dfs[u] = step;
for (vector<int>::iterator iter = g[u].begin(); iter != g[u].end(); iter++) {
step++;
dfs(*iter);
}
end_dfs[u] = step;
}
/********************树状数组模板************************/
int BITree_max = maxn; //数据范围[1,BITree],注意最小值是1,如果为0,请++
int BITree_num[maxn];//maxn为元素的个数
void Update(int i, int value) { //更新结点i的值为value
while (i <= BITree_max) {
BITree_num[i] += value;
i += i & -i;
}
}
int Query(int i) {//查询[1,n]的综合
int ans = 0;
while (i > 0) {
ans += BITree_num[i];
i -= i & -i;
}
return ans;
}
/********************树状数组模板************************/
int main(void) {
int n, m, u, v;
scanf("%d", &n);
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);//建树
}
step = 1;
dfs(1);//dfs序
for (int i = 1; i <= n; i++) {
Update(start_dfs[i], 1);//树状数组
f[i] = 1;//1代表有苹果
}
scanf("%d", &m);
char op;int key;
for (int i = 1; i <= m; i++) {
scanf(" %c%d", &op, &key);//用空格屏蔽换行符,第一次见到
if (op == 'C') {
debug(Query(start_dfs[key]));
Update(start_dfs[key], ((f[key] ^ 1) - f[key]));
debug(Query(start_dfs[key]));
debug(((f[key] ^ 1) - f[key]));
f[key] ^= 1;//0代表无苹果
}
else
cout << Query(end_dfs[key]) - Query(start_dfs[key] - 1) << endl;
}
return 0;
}
------ 本文结束感谢您的阅读 ------
如果觉得我的文章对您有帮助,请随意打赏3元请我买瓶可乐( •̀ ω •́ )。您的支持将鼓励我创作更好的文章。