centroid_decomposition.hpp¶
构造树的点分治层次；适合按距离维护全局动态点集、统计经过重心的路径。
Complexity: Time: O(n log n). Space: O(n).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 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 the centroid tree; fa[rt] is -1 and ord is the
/// decomposition order.
void build(const std::vector<std::vector<int>> &g) {
n = int(g.size());
fa.assign(n, -1);
dep.assign(n, -1);
ord.clear();
if (n == 0) {
rt = -1;
return;
}
std::vector<int> siz(n);
std::vector<bool> del(n);
auto gsz = [&](auto &self, int u, int pre) -> int {
siz[u] = 1;
for (int nxt : g[u]) {
if (nxt != pre && !del[nxt]) {
siz[u] += self(self, nxt, u);
}
}
return siz[u];
};
auto fc = [&](auto &self, int u, int pre, int tot) -> int {
for (int nxt : g[u]) {
if (nxt != pre && !del[nxt] && siz[nxt] > tot / 2) {
return self(self, nxt, u, tot);
}
}
return u;
};
auto dfs = [&](auto &self, int ent, int cf, int cd) -> int {
int tot = gsz(gsz, ent, -1);
int cen = fc(fc, ent, -1, tot);
fa[cen] = cf;
dep[cen] = cd;
ord.push_back(cen);
del[cen] = true;
for (int nxt : g[cen]) {
if (!del[nxt]) {
self(self, nxt, cen, cd + 1);
}
}
return cen;
};
rt = dfs(dfs, 0, -1, 0);
}
};
} // namespace noya
#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 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 the centroid tree; fa[rt] is -1 and ord is the
/// decomposition order.
void build(const std::vector<std::vector<int>> &g) {
n = int(g.size());
fa.assign(n, -1);
dep.assign(n, -1);
ord.clear();
if (n == 0) {
rt = -1;
return;
}
std::vector<int> siz(n);
std::vector<bool> del(n);
auto gsz = [&](auto &self, int u, int pre) -> int {
siz[u] = 1;
for (int nxt : g[u]) {
if (nxt != pre && !del[nxt]) {
siz[u] += self(self, nxt, u);
}
}
return siz[u];
};
auto fc = [&](auto &self, int u, int pre, int tot) -> int {
for (int nxt : g[u]) {
if (nxt != pre && !del[nxt] && siz[nxt] > tot / 2) {
return self(self, nxt, u, tot);
}
}
return u;
};
auto dfs = [&](auto &self, int ent, int cf, int cd) -> int {
int tot = gsz(gsz, ent, -1);
int cen = fc(fc, ent, -1, tot);
fa[cen] = cf;
dep[cen] = cd;
ord.push_back(cen);
del[cen] = true;
for (int nxt : g[cen]) {
if (!del[nxt]) {
self(self, nxt, cen, cd + 1);
}
}
return cen;
};
rt = dfs(dfs, 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 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 the centroid tree; fa[rt] is -1 and ord is the
/// decomposition order.
void build(const std::vector<std::vector<int>> &g) {
n = int(g.size());
fa.assign(n, -1);
dep.assign(n, -1);
ord.clear();
if (n == 0) {
rt = -1;
return;
}
std::vector<int> siz(n);
std::vector<bool> del(n);
auto gsz = [&](auto &self, int u, int pre) -> int {
siz[u] = 1;
for (int nxt : g[u]) {
if (nxt != pre && !del[nxt]) {
siz[u] += self(self, nxt, u);
}
}
return siz[u];
};
auto fc = [&](auto &self, int u, int pre, int tot) -> int {
for (int nxt : g[u]) {
if (nxt != pre && !del[nxt] && siz[nxt] > tot / 2) {
return self(self, nxt, u, tot);
}
}
return u;
};
auto dfs = [&](auto &self, int ent, int cf, int cd) -> int {
int tot = gsz(gsz, ent, -1);
int cen = fc(fc, ent, -1, tot);
fa[cen] = cf;
dep[cen] = cd;
ord.push_back(cen);
del[cen] = true;
for (int nxt : g[cen]) {
if (!del[nxt]) {
self(self, nxt, cen, cd + 1);
}
}
return cen;
};
rt = dfs(dfs, 0, -1, 0);
}
};
} // namespace noya