centroid_decomposition.hpp¶
反复选重心，把树拆成较小子树，得到点分治层次；适合统计树上距离和经过重心的路径。
Complexity: Time: \(O(n \log n)\). Space: \(O(n)\); initial DFS has \(O(\text{tree height})\) call depth.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log n). Space: O(n); initial DFS has O(tree height) call depth.
#include <vector>
namespace noya {
/// @brief Centroid-decomposition tree of an undirected tree (empty is allowed).
/// Input is unchanged; adjacency entries must form a tree with valid vertex IDs.
struct centroid_decomposition {
int n = 0;
int rt = -1;
std::vector<int> fa;
std::vector<int> dep;
std::vector<int> ord;
centroid_decomposition() = default;
explicit centroid_decomposition(const std::vector<std::vector<int>> &g) {
build(g);
}
/// @brief Rebuild; fa[rt] = -1, dep[rt] = 0, ord is decomposition preorder.
/// Of two possible centroids choose the one nearer the component entry
/// (initially 0); visit child components in the centroid's adjacency order.
void build(const std::vector<std::vector<int>> &g) {
n = int(g.size());
fa.assign(n, -1);
dep.assign(n, -1);
ord.clear();
ord.reserve(n);
if (n == 0) {
rt = -1;
return;
}
std::vector<int> size(n, 1);
auto init = [&](auto &self, int u, int p) -> void {
for (int v : g[u]) if (v != p) {
self(self, v, u);
size[u] += size[v];
}
};
init(init, 0, -1);
auto dfs = [&](auto &self, int entry, int parent, int depth) -> int {
int total = size[entry], center = entry;
if (total > 1) {
for (;;) {
int next = -1;
for (int v : g[center]) {
if (dep[v] == -1 && size[v] > total / 2) {
next = v;
break;
}
}
if (next == -1) break;
// Reroot the component across this edge. After deleting its center,
// every neighboring component already has correct subtree sizes.
size[center] -= size[next];
size[next] += size[center];
center = next;
}
}
fa[center] = parent;
dep[center] = depth;
ord.push_back(center);
// The decomposition itself has logarithmic depth.
if (total > 1)
for (int v : g[center])
if (dep[v] == -1) self(self, v, center, depth + 1);
return center;
};
rt = dfs(dfs, 0, -1, 0);
}
};
} // namespace noya
// NOYA_CENTROID_DECOMPOSITION_HPP
#ifndef NOYA_CENTROID_DECOMPOSITION_HPP
#define NOYA_CENTROID_DECOMPOSITION_HPP 1
/// @complexity Time: O(n log n). Space: O(n); initial DFS has O(tree height) call depth.
#include <vector>
namespace noya {
/// @brief Centroid-decomposition tree of an undirected tree (empty is allowed).
/// Input is unchanged; adjacency entries must form a tree with valid vertex IDs.
struct centroid_decomposition {
int n = 0;
int rt = -1;
std::vector<int> fa;
std::vector<int> dep;
std::vector<int> ord;
centroid_decomposition() = default;
explicit centroid_decomposition(const std::vector<std::vector<int>> &g) {
build(g);
}
/// @brief Rebuild; fa[rt] = -1, dep[rt] = 0, ord is decomposition preorder.
/// Of two possible centroids choose the one nearer the component entry
/// (initially 0); visit child components in the centroid's adjacency order.
void build(const std::vector<std::vector<int>> &g) {
n = int(g.size());
fa.assign(n, -1);
dep.assign(n, -1);
ord.clear();
ord.reserve(n);
if (n == 0) {
rt = -1;
return;
}
std::vector<int> size(n, 1);
auto init = [&](auto &self, int u, int p) -> void {
for (int v : g[u]) if (v != p) {
self(self, v, u);
size[u] += size[v];
}
};
init(init, 0, -1);
auto dfs = [&](auto &self, int entry, int parent, int depth) -> int {
int total = size[entry], center = entry;
if (total > 1) {
for (;;) {
int next = -1;
for (int v : g[center]) {
if (dep[v] == -1 && size[v] > total / 2) {
next = v;
break;
}
}
if (next == -1) break;
// Reroot the component across this edge. After deleting its center,
// every neighboring component already has correct subtree sizes.
size[center] -= size[next];
size[next] += size[center];
center = next;
}
}
fa[center] = parent;
dep[center] = depth;
ord.push_back(center);
// The decomposition itself has logarithmic depth.
if (total > 1)
for (int v : g[center])
if (dep[v] == -1) self(self, v, center, depth + 1);
return center;
};
rt = dfs(dfs, 0, -1, 0);
}
};
} // namespace noya
#endif // NOYA_CENTROID_DECOMPOSITION_HPP
/// @complexity Time: O(n log n). Space: O(n); initial DFS has O(tree height) call depth.
#include <vector>
namespace noya {
/// @brief Centroid-decomposition tree of an undirected tree (empty is allowed).
/// Input is unchanged; adjacency entries must form a tree with valid vertex IDs.
struct centroid_decomposition {
int n = 0;
int rt = -1;
std::vector<int> fa;
std::vector<int> dep;
std::vector<int> ord;
centroid_decomposition() = default;
explicit centroid_decomposition(const std::vector<std::vector<int>> &g) {
build(g);
}
/// @brief Rebuild; fa[rt] = -1, dep[rt] = 0, ord is decomposition preorder.
/// Of two possible centroids choose the one nearer the component entry
/// (initially 0); visit child components in the centroid's adjacency order.
void build(const std::vector<std::vector<int>> &g) {
n = int(g.size());
fa.assign(n, -1);
dep.assign(n, -1);
ord.clear();
ord.reserve(n);
if (n == 0) {
rt = -1;
return;
}
std::vector<int> size(n, 1);
auto init = [&](auto &self, int u, int p) -> void {
for (int v : g[u]) if (v != p) {
self(self, v, u);
size[u] += size[v];
}
};
init(init, 0, -1);
auto dfs = [&](auto &self, int entry, int parent, int depth) -> int {
int total = size[entry], center = entry;
if (total > 1) {
for (;;) {
int next = -1;
for (int v : g[center]) {
if (dep[v] == -1 && size[v] > total / 2) {
next = v;
break;
}
}
if (next == -1) break;
// Reroot the component across this edge. After deleting its center,
// every neighboring component already has correct subtree sizes.
size[center] -= size[next];
size[next] += size[center];
center = next;
}
}
fa[center] = parent;
dep[center] = depth;
ord.push_back(center);
// The decomposition itself has logarithmic depth.
if (total > 1)
for (int v : g[center])
if (dep[v] == -1) self(self, v, center, depth + 1);
return center;
};
rt = dfs(dfs, 0, -1, 0);
}
};
} // namespace noya
// NOYA_CENTROID_DECOMPOSITION_HPP