木の平方分割
概要
木を大きさ高々 $B$ の部分木に分解し，$O(\frac{N}{B})$ の木からなる森を作る．こうすると $O(N)$ のクエリが $O(\frac{N}{B} + B)$ で処理できることがある． 分解するには，根から BFS をして最初のブロックをとり，別れた森のそれぞれの根から BFS をして… を繰り返す．下の例は LCA をクエリあたり $O(\sqrt N)$ で処理する例．
計算量
構築 $O(N)$．クエリあたり $O(\sqrt N)$．
計算量
tree_sqrt_decomp tree(N)- 大きさ N の辺なしグラフを作る
tree.add_edge(u,v)- 無向辺 (u, v) を追加する
tree.decomp(root, B)- root を根として大きさ B の木に分割する
tree.lca(u,v)- u と v の LCA を求める
tree.parent[v]- v の親
tree.color[v]- v が属するブロック
tree.go_up[v]- v が属するブロックの根の親
tree.root_depth[v]- v が属するブロックの根の深さ
実装
const int B = 512;
struct sqrt_decomp_tree {
int n;
int size() const { return n; }
std::vector<int> color, parent, depth, root_depth, go_up, visited;
std::vector<std::vector<int>> g;
sqrt_decomp_tree(int n_) : n(n_), g(n) {}
void add_edge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
void decomp(int root = 0) {
parent.assign(n, -1);
depth.assign(n, 0);
root_depth.assign(n, 0);
go_up.assign(n, -1);
visited.assign(n, false);
std::vector<int> tord;
std::vector<int> q(n + 1);
int l = 0, r = 0;
q[r++] = root;
while (l != r) {
int v = q[l++];
visited[v] = true;
tord.push_back(v);
for (int c : g[v]) {
if (!visited[c]) {
parent[c] = v;
depth[c] = depth[v] + 1;
q[r++] = c;
}
}
}
std::swap(color, visited); // メモリをケチる
color.assign(n, -1);
int c = 0;
for (int u : tord) {
if (color[u] != -1) continue;
l = 0, r = 0;
q[r++] = u;
for (int i = 0; i < B && l != r; i++) {
int v = q[l++];
color[v] = c;
go_up[v] = parent[u];
root_depth[v] = depth[u];
for (int c : g[v])
if (color[c] == -1) q[r++] = c;
}
c++;
}
}
int lca(int u, int v) {
while (root_depth[u] > root_depth[v]) u = go_up[u];
while (root_depth[u] < root_depth[v]) v = go_up[v];
while (depth[u] > depth[v]) u = parent[u];
while (depth[u] < depth[v]) v = parent[v];
while (u != v) u = parent[u], v = parent[v];
return u;
}
};