URAL 2030 Awesome Backup System(BFS序 + 树状数组)

题目大意

给定一棵有 $n$ 个结点的树,询问 $m$ 次,操作分为两种:

  • 1 v 使结点 $v$ 的所有邻接顶点的权值增加 $a_i$
  • 2 v 查询结点 $v$ 的权值

$(1 \leq n \leq 10^5, 0 \leq a \leq 10^9,1 \leq m \leq 10^5)$

解题思路

BFS序 + 树状数组

利用BFS序对树的结点编号,对于每个结点 $v$,记录其父亲结点 $pa[v]$ 和 儿子结点的区间。然后用树状数组/线段树实现区间更新、单点查询就可以了。

代码如下:

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MAXM = 1e5 + 10;
const int MOD = 1e9 + 7;

struct edge {
int to, next;
edge( int to = 0, int next = 0 ) : to(to), next(next) {}
} G[MAXM << 1];
int n;
ll a[MAXN];
int tot, head[MAXN];
int id[MAXN], par[MAXN], son[MAXN][2];
ll bit[MAXN];

ll sum(int i)
{

ll s = 0;
while( i > 0 )
{
s = (s + bit[i] + MOD) % MOD;
i -= i & -i;
}
return s;
}
void add(int i, ll x)
{

while( i <= n )
{
bit[i] = (bit[i] + x + MOD) % MOD;
i += i & -i;
}
}
void bfs(int s)
{

int clk = 0;
queue<int> que;
que.push(s);
par[s] = 0;
id[s] = ++clk;
while( !que.empty() )
{
int u = que.front(); que.pop();
son[u][0] = clk;
for( int i = head[u]; ~i; i = G[i].next )
{
int v = G[i].to;
if( v == par[u] ) continue;
que.push(v);
par[v] = u;
id[v] = ++clk;
}
son[u][1] = clk;
}
}
void add_edge(int u, int v)
{

G[tot] = edge(v, head[u]);
head[u] = tot++;
G[tot] = edge(u, head[v]);
head[v] = tot++;
}
void init()
{

tot = 0;
memset(head, -1, sizeof(head));
}
int main()
{

while( ~scanf("%d", &n) )
{
init();
for( int i = 1; i <= n; ++ i ) scanf("%I64d", a + i);
int u, v;
for( int i = 0; i < n - 1; ++ i )
{
scanf("%d %d", &u, &v);
add_edge(u, v);
}
bfs(1);
memset(bit, 0, sizeof(bit));
for( int i = 1; i <= n; ++ i )
{
add(id[i], a[i]);
add(id[i] + 1, -a[i]);
}
int m;
scanf("%d", &m);
for( int i = 0; i < m; ++ i )
{
scanf("%d %d", &u, &v);
ll x = sum(id[v]);
if( u == 1 )
{
if( par[v] )
{
add(id[par[v]], x);
add(id[par[v]] + 1, -x);
}
if( son[v][0] != son[v][1] )
{
add(son[v][0] + 1, x);
add(son[v][1] + 1, -x);
}
}
else
{
printf("%I64d\n", x);
}
}
}
return 0;
}


另一种做法

待更新…

如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!