b327. 學姊日談

contents

  1. 1. 內容 :
  2. 2. 輸入說明 :
  3. 3. 輸出說明 :
  4. 4. 範例輸入 :
  5. 5. 範例輸出 :
  6. 6. Solution 1
  7. 7. Solution 2

內容 :

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話,就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下,詢問次數肯定比調整次數來得高,想一想常數還得加上去,完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹,有比較好做嗎?說不定有更簡化的算法來完成?』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎?我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree,也就是說需要將節點編號重新編成有大小關係,然後維護一個 BST 來查找 lower_bound 的結果,這麼一來就是 O(k log n) - O(log n) 了!』
『啊啊啊,這個方法不可行,』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了,既然暴力法有期望值的剪枝,讓它剪不了不就好了!』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係,吾等 M 可不是說假的』
Problem

給定一棵樹,樹根 root 編號 0,每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k,請輸出從 x 到 root 的權重和。

輸入說明 :

輸入有多組測資,每組測資第一行會有一個整數 N (N < 32767),表示這棵樹有多少個節點。

接下來會有 N - 1 行,每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767),表示接下來有 M 組詢問。

輸出說明 :

對於每個詢問結果輸出一行,請參照範例輸出的說明。

每組測資後空一行,保證總和可以在 signed 32 bits 內。

範例輸入 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
10
0 1
0 2
1 3
0 4
3 5
4 6
5 7
5 8
4 9
5
1 1
5 2
3 0
0 4
4 8

範例輸出 :

1
2
3
4
5
1
3
1
4
12

Solution 1

先將一棵樹壓平,壓平的方式為採用前序走訪。壓樹的另一個思考方式就是換成括弧表示法。(A (B) (C(D)(E))) 類似的情況。壓樹之後,每個節點對應一個左右括弧位置,當我們增加節點 v 權重時,相當於將所有區間的內數字加上 k (子樹的所有節點到根的花費)。

因此我們的問題變成

  • 操作 [l, r]:將區間內的所有數字加上 k
  • 詢問 x:詢問位置 x 元素的值。

下面使用 Binary indexed tree 示範區間調整,單點詢問。

對於 ADD [l, r] k 時,相當於 BIT[l] += k, BIT[r+1] -= k,單點詢問相當於找前綴和 [1, x] 的結果。

每個操作時間複雜度 O(log n)

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
#include <stdio.h>
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
struct Tree {
vector<int> g[MAXN];
int root;
void init(int n) {
for (int i = 0; i < n; i++)
g[i].clear();
root = 0;
}
void addEdge(int x, int y) {
g[x].push_back(y);
g[y].push_back(x);
}
} tree;
int bPos[MAXN], ePos[MAXN], inOrder[MAXN<<1], inIdx = 0;
void prepare(int u, int p) {
bPos[u] = ePos[u] = ++inIdx, inOrder[inIdx] = u;
for (int i = 0; i < tree.g[u].size(); i++) {
int v = tree.g[u][i];
if (v == p) continue;
prepare(v, u);
}
ePos[u] = ++inIdx, inOrder[inIdx] = u;
}
int bitTree[MAXN<<1];
void modify(int x, int N, int val) {
while (x <= N) {
bitTree[x] += val;
x += x&(-x);
}
}
int query(int x) {
int ret = 0;
while (x) {
ret += bitTree[x];
x -= x&(-x);
}
return ret;
}
int main() {
int n, q, x, y;
char cmd[10];
while (scanf("%d", &n) == 1) {
tree.init(n);
int on[MAXN] = {};
for (int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
tree.addEdge(x, y);
}
inIdx = 0;
prepare(tree.root = 0, -1);
memset(bitTree, 0, sizeof(bitTree));
scanf("%d", &q);
for (int i = 0; i < q; i++) {
scanf("%d %d", &x, &y);
modify(bPos[x], inIdx, y);
modify(ePos[x] + 1, inIdx, -y);
printf("%d\n", query(bPos[x]));
}
puts("");
}
return 0;
}

Solution 2

這個解法直接使用樹鏈剖分,樹鏈剖分將子樹節點數量最大的當作重邊,其餘皆為輕邊。將以重邊相連的所有節點,看似一個鏈狀,當作一個 1D Array 看待。

保證每個點爬到 root,只會經過 log n 的輕邊,而中間鏈狀處理,可以使用 segment tree 等之類的樹來壓縮處理時間。

下面為樹鏈剖分的解法,詢問效率 O(log^2 n),調整 O(log n)

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
#include <stdio.h>
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
int hNext[MAXN], iNode[MAXN], aPos[MAXN];
int used[MAXN], nodesize = 0;
struct Node {
int p, pPos;
vector<int> A;
vector<int> BIT;
void init() {
A.clear(), BIT.clear();
p = -1;
}
} nodes[262144];
struct Tree {
vector<int> g[MAXN];
int root;
void init(int n) {
for (int i = 0; i < n; i++)
g[i].clear();
root = 0;
}
void addEdge(int x, int y) {
g[x].push_back(y);
g[y].push_back(x);
}
} tree;
int prepare(int u, int p) {
int sz = 1, mx = 0, hedge = -1;
int v, t;
for (int i = 0; i < tree.g[u].size(); i++) {
v = tree.g[u][i], t;
if (v == p) continue;
sz += (t = prepare(v, u));
if (mx < t)
mx = t, hedge = v;
}
hNext[u] = hedge;
return sz;
}
void build(int u, int p) {
if (used[u] == 0) {
Node &nd = nodes[++nodesize];
nd.init();
for (int i = u; i != -1; i = hNext[i]) {
used[i] = 1;
iNode[i] = nodesize, aPos[i] = nd.A.size();
nd.A.push_back(i);
}
nd.BIT.clear(), nd.BIT.resize(nd.A.size() + 10, 0);
if (p != -1) nd.p = iNode[p], nd.pPos = aPos[p];
}
int v;
for (int i = 0; i < tree.g[u].size(); i++) {
v = tree.g[u][i];
if (v == p) continue;
build(v, u);
}
}
int queryBIT(vector<int> &BIT, int x) {
int ret = 0;
while (x)
ret += BIT[x], x -= x&(-x);
return ret;
}
void modifyBIT(vector<int> &BIT, int x, int val, int L) {
while (x <= L)
BIT[x] += val, x += x&(-x);
}
void search(int u) {
int sum = 0;
set< pair<int, int> >::iterator it, jt;
for (int i = iNode[u], in = aPos[u]; i != -1; in = nodes[i].pPos, i = nodes[i].p)
sum += queryBIT(nodes[i].BIT, in + 1);
printf("%d", sum);
puts("");
}
void modify(int u, int val) {
Node &nd = nodes[iNode[u]];
int pos = aPos[u];
modifyBIT(nd.BIT, pos + 1, val, nd.A.size());
}
int main() {
int n, q, x, y;
char cmd[10];
while (scanf("%d", &n) == 1) {
tree.init(n);
int on[MAXN] = {};
for (int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
tree.addEdge(x, y);
}
prepare(tree.root = 0, -1);
memset(used, 0, sizeof(used));
nodesize = 0;
build(tree.root = 0, -1);
scanf("%d", &q);
for (int i = 0; i < q; i++) {
scanf("%d %d", &x, &y);
modify(x, y);
search(x);
}
puts("");
}
return 0;
}