樹分塊
樹分塊的方式
可以參考 真 - 樹上莫隊。
也可以參考 ouuan 的博客/莫隊、帶修莫隊、樹上莫隊詳解/樹上莫隊。
樹上莫隊同樣可以參考以上兩篇文章。
樹分塊的應用
樹分塊除了應用於莫隊，還可以靈活地運用到某些樹上問題中。但可以用樹分塊解決的題目往往都有更優秀的做法，所以相關的題目較少。
順帶提一句，「gty 的妹子樹」的樹分塊做法可以被菊花圖卡掉。
先進行樹分塊，然後對每個塊的關鍵點，預處理出它到祖先中每個關鍵點的路徑上顏色的 bitset，以及每個關鍵點的最近關鍵點祖先，複雜度是 \(O(n\sqrt n+\frac{nc}{32})\)，其中 \(n\sqrt n\) 是暴力從每個關鍵點向上跳的複雜度，\(\frac{nc}{32}\) 是把 \(O(n)\) 個 bitset 存下來的複雜度。
回答詢問的時候，先從路徑的端點暴力跳到所在塊的關鍵點，再從所在塊的關鍵點一塊一塊地向上跳，直到 \(lca\) 所在塊，然後再暴力跳到 \(lca\)。關鍵點之間的 bitset 已經預處理了，剩下的在暴力跳的過程中計算。單次詢問複雜度是 \(O(\sqrt n+\frac c{32})\)，其中 \(\sqrt n\) 是塊內暴力跳以及塊直接向上跳的複雜度，\(O(\frac c{32})\) 是將預處理的結果與暴力跳的結果合併的複雜度。數顏色個數可以用 bitset 的 count()，求 \(\operatorname{mex}\) 可以用 bitset 的 _Find_first()。
所以，總複雜度為 \(O((n+m)(\sqrt n+\frac c{32}))\)。
參考代碼
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
127
128
129
130
131
132
133
134
135
136
137
138 | #include <algorithm>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <iostream>
using namespace std;
int read() {
int out = 0;
char c;
while (!isdigit(c = getchar()))
;
for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
return out;
}
const int N = 100010;
const int B = 666;
const int C = 30000;
void add(int u, int v);
void dfs(int u);
int head[N], nxt[N << 1], to[N << 1], cnt;
int n, m, type, c[N], fa[N], dep[N], sta[N], top, tot, bl[N], key[N / B + 5],
p[N], keyid[N];
bool vis[N];
bitset<C> bs[N / B + 5][N / B + 5], temp;
int main() {
int i, u, v, x, y, k, lastans = 0;
n = read();
m = read();
type = read();
for (i = 1; i <= n; ++i) c[i] = read();
for (i = 1; i < n; ++i) {
u = read();
v = read();
add(u, v);
add(v, u);
}
dfs(1);
if (!tot) ++tot;
if (keyid[key[tot]] == tot) keyid[key[tot]] = 0;
key[tot] = 1;
keyid[1] = tot;
while (top) bl[sta[top--]] = tot;
for (i = 1; i <= tot; ++i) { // 预处理
if (vis[key[i]]) continue;
vis[key[i]] = true;
temp.reset();
for (u = key[i]; u; u = fa[u]) {
temp[c[u]] = 1;
if (keyid[u]) {
if (!p[key[i]] && u != key[i]) p[key[i]] = u;
bs[keyid[key[i]]][keyid[u]] = temp;
}
}
}
while (m--) {
k = read();
temp.reset();
while (k--) {
u = x = read() ^ lastans;
v = y = read() ^ lastans;
while (key[bl[x]] != key[bl[y]]) {
if (dep[key[bl[x]]] > dep[key[bl[y]]]) {
if (x == u) { // 若是第一次跳先暴力跳到关键点
while (x != key[bl[u]]) {
temp[c[x]] = 1;
x = fa[x];
}
} else
x = p[x]; // 否则跳一整块
} else {
if (y == v) {
while (y != key[bl[v]]) {
temp[c[y]] = 1;
y = fa[y];
}
} else
y = p[y];
}
}
if (keyid[x]) temp |= bs[keyid[key[bl[u]]]][keyid[x]];
if (keyid[y]) temp |= bs[keyid[key[bl[v]]]][keyid[y]];
while (x != y) {
if (dep[x] > dep[y]) {
temp[c[x]] = 1;
x = fa[x];
} else {
temp[c[y]] = 1;
y = fa[y];
}
}
temp[c[x]] = true;
}
int ans1 = temp.count(), ans2 = (~temp)._Find_first();
printf("%d %d\n", ans1, ans2);
lastans = (ans1 + ans2) * type;
}
return 0;
}
void dfs(int u) { // 根据题意找点
int i, v, t = top;
for (i = head[u]; i; i = nxt[i]) {
v = to[i];
if (v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
dfs(v);
if (top - t >= B) {
key[++tot] = u;
if (!keyid[u]) keyid[u] = tot;
while (top > t) bl[sta[top--]] = tot;
}
}
sta[++top] = u;
}
void add(int u, int v) {
nxt[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
}
|
這題和上一題基本一樣，唯一的區別是得到 bitset 後如何計算答案。
由於 BZOJ 是計算所有測試點總時限，不好卡，所以可以用 _Find_next() 水過去。
正解是每 \(16\) 位一起算，先預處理出 \(2^{16}\) 種可能的情況高位連續 \(1\) 的個數、低位連續 \(1\) 的個數以及中間的貢獻。只不過這樣要手寫 bitset，因為標準庫的 bitset 不能取某 \(16\) 位……
代碼可以參考 這篇博客。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：ouuan, Ir1d, Marcythm, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用