重心分解
(library/graph/tree/centroid_decomposition.hpp)

• View this file on GitHub
• Last update: 2026-01-21 19:52:16+09:00
• Include: #include "library/graph/tree/centroid_decomposition.hpp"

重心分解

できること

• 重心分解とは、以下を再帰的に行い、木を階層構造に作り替える
  1. 現在の木から重心を見つける
  2. 重心でポッキリする。（重心を「分解後の木の根」とし、重心を木から取り除く）
  3. 分割した各々の木に対して、1から繰り返す
• 重心で分けるたび部分木のサイズが半分以下になるため、再帰の深さは必ず対数オーダーに収まる
• これにより、「重心分解ツリー」が作られる
  • 元の木における任意の2頂点間のパスは、重心分解ツリーにおける「ある頂点の共通の先祖」を経由するものとして分類できる
  • 木の分割統治ができるため「木上のパスのうち条件 $X$ を満たすものはいくつか？」等が高速で求まる

計算量

• 構築: $O(V \log V)$

使い方

int N, M;
CentroidDecomposition cd(N);
cd.read(M); // グラフ構造体と同様に作成

// 重心分解を実行。戻り値は重心分解ツリー全体の根
int root = cd.build();

// cd.tree に重心分解後の親子関係が格納される
// ex) cd.tree.g[u] には、重心分解ツリーにおける u の子リストが入る

Depends on

• 辺 (library/graph/base/edge.hpp)
• グラフ (library/graph/base/graph.hpp)

Verified with

• 木 - 重心分解のテスト (tests/graph.tree.centroid_decomposition.test.cpp)
• 木 - 重心分解のテスト2 (tests/graph.tree.centroid_decomposition2.test.cpp)

Code

#pragma once
#include "library/graph/base/graph.hpp"
struct CentroidDecomposition : Graph {
  public:
    using Graph::G;
    using Graph::Graph;
    Graph tree;
    int build() {
        sub.assign(G.size(), 0ll);
        v.assign(G.size(), 0ll);
        tree = Graph(G.size());
        return build_dfs(0ll);
    }
    explicit CentroidDecomposition(const Graph &G) : Graph(G) {}

  private:
    vector<int> sub;
    vector<int> v;
    inline int build_dfs(int idx, int par) {
        sub[idx] = 1;
        for (auto &&edge : G[idx]) {
            if (edge.to == par or v[edge.to]) continue;
            sub[idx] += build_dfs(edge.to, idx);
        }
        return sub[idx];
    }
    inline int search_centroid(int idx, int par, const int mid) {
        for (auto &&edge : G[idx]) {
            if (edge.to == par or v[edge.to]) continue;
            if (sub[edge.to] > mid) return search_centroid(edge.to, idx, mid);
        }
        return idx;
    }
    inline int build_dfs(int idx) {
        int centroid = search_centroid(idx, -1, build_dfs(idx, -1) / 2ll);
        v[centroid] = true;
        for (auto &&edge : G[centroid]) {
            if (!v[edge.to]) tree.add(centroid, build_dfs(edge.to));
        }
        v[centroid] = false;
        return centroid;
    }
};

#line 2 "library/graph/base/edge.hpp"
struct Edge {
    int from, to;
    long long cost;
    int idx;
    Edge(int from, int to, long long cost = 1, int idx = -1)
        : from(from), to(to), cost(cost), idx(idx) {}
};
#line 3 "library/graph/base/graph.hpp"
struct Graph {
    int N;
    vector<vector<Edge>> G;
    int es;
    Graph() = default;
    Graph(int N) : N(N), G(N), es(0) {}
    const vector<Edge> &operator[](int v) const { return G[v]; }
    int size() const { return N; }
    void add(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es++));
    }
    void add_both(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es));
        G[to].push_back(Edge(to, from, cost, es++));
    }
    void read(int M, int padding = -1, bool weighted = false,
              bool directed = false) {
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            u += padding, v += padding;
            long long cost = 1ll;
            if (weighted) cin >> cost;
            if (directed) {
                add(u, v, cost);
            } else {
                add_both(u, v, cost);
            }
        }
    }
};
#line 3 "library/graph/tree/centroid_decomposition.hpp"
struct CentroidDecomposition : Graph {
  public:
    using Graph::G;
    using Graph::Graph;
    Graph tree;
    int build() {
        sub.assign(G.size(), 0ll);
        v.assign(G.size(), 0ll);
        tree = Graph(G.size());
        return build_dfs(0ll);
    }
    explicit CentroidDecomposition(const Graph &G) : Graph(G) {}

  private:
    vector<int> sub;
    vector<int> v;
    inline int build_dfs(int idx, int par) {
        sub[idx] = 1;
        for (auto &&edge : G[idx]) {
            if (edge.to == par or v[edge.to]) continue;
            sub[idx] += build_dfs(edge.to, idx);
        }
        return sub[idx];
    }
    inline int search_centroid(int idx, int par, const int mid) {
        for (auto &&edge : G[idx]) {
            if (edge.to == par or v[edge.to]) continue;
            if (sub[edge.to] > mid) return search_centroid(edge.to, idx, mid);
        }
        return idx;
    }
    inline int build_dfs(int idx) {
        int centroid = search_centroid(idx, -1, build_dfs(idx, -1) / 2ll);
        v[centroid] = true;
        for (auto &&edge : G[centroid]) {
            if (!v[edge.to]) tree.add(centroid, build_dfs(edge.to));
        }
        v[centroid] = false;
        return centroid;
    }
};

Back to top page