重心分解 (lib/tree/centroid_decomposition.hpp)

• View this file on GitHub
• Last update: 2025-06-13 13:22:21+09:00
• Include: #include "lib/tree/centroid_decomposition.hpp"

Depends on

• 重み付きグラフ (lib/graph/graph.hpp)
• lib/template/template.hpp

Code

#include "graph/graph.hpp"
#include "template/template.hpp"

/**
 * @brief 重心分解
 *
 * @tparam T 辺の重みの型
 * @param g グラフ
 * @return std::vector<int> 親の頂点
 */
template <class T>
std::vector<int> centroid_decomposition(const Graph<T> &g) {
    int n = g.size();
    std::vector<int> par(n, -1), size(n), size_par(n, -2);
    std::vector<bool> used(n, false);
    auto dfs = [&](auto self, int x, int p) -> int {
        if (size_par[x] == p) return size[x];
        int sum = 1;
        for (auto e : g[x]) {
            if (used[e.to()] || e.to() == p) continue;
            sum += self(self, e.to(), x);
        }
        size_par[x] = p;
        return size[x] = sum;
    };
    auto build = [&](auto self, int x, int p) -> void {
        int sz = dfs(dfs, x, p);
        bool is_centroid = false;
        while (!is_centroid) {
            is_centroid = true;
            for (auto e : g[x]) {
                if (size[e.to()] > size[x] || size[e.to()] * 2 <= sz) continue;
                x = e.to();
                is_centroid = false;
                break;
            }
        }
        par[x] = p;
        used[x] = true;
        for (auto e : g[x]) {
            if (used[e.to()]) continue;
            self(self, e.to(), x);
        }
    };

    build(build, 0, -1);

    return par;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/graph.hpp: line -1: no such header

Back to top page