centroid_decomposition.hpp¶
Centroid-decomposition tree of an undirected tree.
构造树的点分治层次；适合按距离维护全局动态点集、统计经过重心的路径。
Implementation¶
#ifndef NOYA_CENTROID_DECOMPOSITION_HPP
#define NOYA_CENTROID_DECOMPOSITION_HPP 1
/// @complexity Time: O(n log n).
/// Space: O(n).
#include <cassert>
#include <vector>
namespace noya {
/// @brief Centroid-decomposition tree of an undirected tree.
struct centroid_decomposition {
int n = 0;
int root = -1;
std::vector<int> parent;
std::vector<int> level;
std::vector<int> order;
centroid_decomposition() = default;
explicit centroid_decomposition(const std::vector<std::vector<int>> &graph) {
build(graph);
}
/// @brief Rebuild the centroid tree; parent[root] is -1 and order is the
/// decomposition order.
void build(const std::vector<std::vector<int>> &graph) {
n = int(graph.size());
parent.assign(n, -1);
level.assign(n, -1);
order.clear();
if (n == 0) {
root = -1;
return;
}
std::vector<int> subtree_size(n);
std::vector<bool> removed(n);
auto compute_size = [&](auto &self, int vertex, int previous) -> int {
subtree_size[vertex] = 1;
for (int next : graph[vertex]) {
if (next != previous && !removed[next]) {
subtree_size[vertex] += self(self, next, vertex);
}
}
return subtree_size[vertex];
};
auto find_centroid = [&](auto &self, int vertex, int previous,
int total) -> int {
for (int next : graph[vertex]) {
if (next != previous && !removed[next] &&
subtree_size[next] > total / 2) {
return self(self, next, vertex, total);
}
}
return vertex;
};
auto decompose = [&](auto &self, int entry, int centroid_parent,
int centroid_level) -> int {
int total = compute_size(compute_size, entry, -1);
int centroid = find_centroid(find_centroid, entry, -1, total);
parent[centroid] = centroid_parent;
level[centroid] = centroid_level;
order.push_back(centroid);
removed[centroid] = true;
for (int next : graph[centroid]) {
if (!removed[next]) {
self(self, next, centroid, centroid_level + 1);
}
}
return centroid;
};
root = decompose(decompose, 0, -1, 0);
}
};
} // namespace noya
#endif // NOYA_CENTROID_DECOMPOSITION_HPP
#include <cassert>
#include <vector>
/// @complexity Time: O(n log n).
/// Space: O(n).
namespace noya {
/// @brief Centroid-decomposition tree of an undirected tree.
struct centroid_decomposition {
int n = 0;
int root = -1;
std::vector<int> parent;
std::vector<int> level;
std::vector<int> order;
centroid_decomposition() = default;
explicit centroid_decomposition(const std::vector<std::vector<int>> &graph) {
build(graph);
}
/// @brief Rebuild the centroid tree; parent[root] is -1 and order is the
/// decomposition order.
void build(const std::vector<std::vector<int>> &graph) {
n = int(graph.size());
parent.assign(n, -1);
level.assign(n, -1);
order.clear();
if (n == 0) {
root = -1;
return;
}
std::vector<int> subtree_size(n);
std::vector<bool> removed(n);
auto compute_size = [&](auto &self, int vertex, int previous) -> int {
subtree_size[vertex] = 1;
for (int next : graph[vertex]) {
if (next != previous && !removed[next]) {
subtree_size[vertex] += self(self, next, vertex);
}
}
return subtree_size[vertex];
};
auto find_centroid = [&](auto &self, int vertex, int previous,
int total) -> int {
for (int next : graph[vertex]) {
if (next != previous && !removed[next] &&
subtree_size[next] > total / 2) {
return self(self, next, vertex, total);
}
}
return vertex;
};
auto decompose = [&](auto &self, int entry, int centroid_parent,
int centroid_level) -> int {
int total = compute_size(compute_size, entry, -1);
int centroid = find_centroid(find_centroid, entry, -1, total);
parent[centroid] = centroid_parent;
level[centroid] = centroid_level;
order.push_back(centroid);
removed[centroid] = true;
for (int next : graph[centroid]) {
if (!removed[next]) {
self(self, next, centroid, centroid_level + 1);
}
}
return centroid;
};
root = decompose(decompose, 0, -1, 0);
}
};
} // namespace noya