重心分解
(tree/centroid-decomposition.hpp)

• View this file on GitHub
• Last update: 2026-08-26 13:48:57+09:00
• Include: #include "tree/centroid-decomposition.hpp"

木を重心分解する．

CentroidDecomposition(g) は重心分解木の根と親配列の組を返す．入力 g は $1$ 頂点以上の木とする．親配列では根の親を $-1$ とする．

構築は $O(N\log N)$ 時間，空間計算量は $O(N)$．

Depends on

• Compressed Sparse Row (graph/csr.hpp)

Verified with

• verify/tree/UNIT_centroid_decomposition.test.cpp

Code

#pragma once

#include "graph/csr.hpp"

pair<int, vector<int>> CentroidDecomposition(const CSR<int>& g) {
  const int n = g.size();
  vector<int> parent(n, -1), bfs(n);
  int bfsi = 1;
  for (auto x : bfs)
    for (auto y : g[x])
      if (y != parent[x]) parent[y] = x, bfs[bfsi++] = y;
  vector<int> sz(n, 1);
  for (int i = n - 1; i > 0; i--) sz[parent[bfs[i]]] += sz[bfs[i]];
  bfsi = 1;
  for (auto x : bfs) {
    while (true) {
      int nx = -1;
      for (auto y : g[x])
        if (sz[y] * 2 > sz[x]) nx = y;
      if (nx == -1) break;
      parent[nx] = parent[x];
      parent[x] = nx;
      sz[x] -= sz[nx];
      sz[nx] += sz[x];
      x = nx;
    }
    sz[x] = 0;
    for (auto y : g[x])
      if (sz[y] != 0) bfs[bfsi++] = y;
  }
  int root = 0;
  while (parent[root] != -1) root++;
  return {root, parent};
}

template <class G>
pair<int, vector<int>> CentroidDecomposition(const G& g) {
  return CentroidDecomposition(CSR<int>(g));
}

/**
 * @brief 重心分解
 * @docs docs/tree/centroid-decomposition.md
 */

#line 2 "tree/centroid-decomposition.hpp"

#line 2 "graph/csr.hpp"

// Compressed Sparse Row format
template <class E>
struct CSR {
  CSR() : start(1, 0) {}
  template <class G>
  CSR(const G& g) {
    if constexpr (is_same_v<E, int>)
      build_simple(g);
    else
      build(g);
  }
  size_t size() const { return start.size() - 1; }
  size_t edge_count() const { return edges.size(); }
  span<const E> operator[](int x) const {
    assert(0 <= x && x < static_cast<int>(size()));
    return span<const E>(edges).subspan(start[x], start[x + 1] - start[x]);
  }
  template <class G>
  void build(const G& g) {
    int n = g.size();
    start.assign(n + 1, 0);
    for (int i = 0; i < n; i++) start[i + 1] = start[i] + g[i].size();
    edges.clear();
    edges.reserve(start[n]);
    for (int x = 0; x < n; x++)
      for (const auto& e : g[x]) edges.push_back(e);
  }
  template <class G>
  void build_simple(const G& g) {
    static_assert(is_same_v<E, int>);
    int n = g.size();
    start.assign(n + 1, 0);
    for (int i = 0; i < n; i++) start[i + 1] = start[i] + g[i].size();
    edges.clear();
    edges.reserve(start[n]);
    for (int x = 0; x < n; x++)
      for (const auto& e : g[x]) edges.push_back(e.to);
  }

 private:
  vector<E> edges;
  vector<int> start;
};

/**
 * @brief Compressed Sparse Row
 * @docs docs/graph/csr.md
 */
#line 4 "tree/centroid-decomposition.hpp"

pair<int, vector<int>> CentroidDecomposition(const CSR<int>& g) {
  const int n = g.size();
  vector<int> parent(n, -1), bfs(n);
  int bfsi = 1;
  for (auto x : bfs)
    for (auto y : g[x])
      if (y != parent[x]) parent[y] = x, bfs[bfsi++] = y;
  vector<int> sz(n, 1);
  for (int i = n - 1; i > 0; i--) sz[parent[bfs[i]]] += sz[bfs[i]];
  bfsi = 1;
  for (auto x : bfs) {
    while (true) {
      int nx = -1;
      for (auto y : g[x])
        if (sz[y] * 2 > sz[x]) nx = y;
      if (nx == -1) break;
      parent[nx] = parent[x];
      parent[x] = nx;
      sz[x] -= sz[nx];
      sz[nx] += sz[x];
      x = nx;
    }
    sz[x] = 0;
    for (auto y : g[x])
      if (sz[y] != 0) bfs[bfsi++] = y;
  }
  int root = 0;
  while (parent[root] != -1) root++;
  return {root, parent};
}

template <class G>
pair<int, vector<int>> CentroidDecomposition(const G& g) {
  return CentroidDecomposition(CSR<int>(g));
}

/**
 * @brief 重心分解
 * @docs docs/tree/centroid-decomposition.md
 */

Back to top page