重心分解 (centroid decompositon)
(include/emthrm/graph/tree/centroid_decomposition.hpp)

• View this file on GitHub
• Last update: 2023-02-27 17:26:42+09:00
• Include: #include "emthrm/graph/tree/centroid_decomposition.hpp"

重心を基にした木の分解法の一つである。木上で分割統治法を行うときに有用である。

時間計算量

$O(\lvert V \rvert \log{\lvert V \rvert})$

仕様

template <typename CostType>
struct CentroidDecomposition;

• CostType：辺のコストを表す型

メンバ変数

名前	説明
int root	重心分解した木の根
std::vector<int> parent	parent[i] は g における頂点 $i$ の親を表す。ただし存在しないときは $-1$ となる。
std::vector<std::vector<int>> g	重心分解を行った木

メンバ関数

名前	効果
explicit CentroidDecomposition(const std::vector<std::vector<Edge<CostType>>>& graph);	木 $\mathrm{graph}$ に対してオブジェクトを構築する。

参考文献

• http://compro.tsutajiro.com/archive/190207_divcon.pdf
• https://lumakernel.github.io/ecasdqina/graph/CentroidDecomposition

TODO

• https://twitter.com/beet_aizu/status/1142651943971540992
• $1/3$ 重心分解
  • https://maspypy.com/%e9%87%8d%e5%bf%83%e5%88%86%e8%a7%a3%e3%83%bb1-3%e9%87%8d%e5%bf%83%e5%88%86%e8%a7%a3%e3%81%ae%e3%81%8a%e7%b5%b5%e6%8f%8f%e3%81%8d
  • https://twitter.com/noshi91/status/1549081194859761664
  • https://twitter.com/NachiaVivias/status/1549184577511788544
  • https://twitter.com/SSRS_cp/status/1640566437734653953
  • https://twitter.com/noshi91/status/1640569780100034560
  • https://twitter.com/noshi91/status/1673744350998851584
  • https://twitter.com/noshi91/status/1683485568737345543
  • https://twitter.com/noshi91/status/1720487757238432233
  • https://twitter.com/noshi91/status/1758542680517476658
  • 問題例 “Paken Land”
    • https://atcoder.jp/contests/pakencamp-2022-day1/submissions/40109596
  • 問題例 “Tree Distance 3”

Submissons

https://atcoder.jp/contests/abc291/submissions/39252522

Depends on

• 辺 (include/emthrm/graph/edge.hpp)

Verified with

• グラフ/木/重心分解 (test/graph/tree/centroid_decomposition.test.cpp)

Code

#ifndef EMTHRM_GRAPH_TREE_CENTROID_DECOMPOSITION_HPP_
#define EMTHRM_GRAPH_TREE_CENTROID_DECOMPOSITION_HPP_

#include <ranges>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
struct CentroidDecomposition {
  int root;
  std::vector<int> parent;
  std::vector<std::vector<int>> g;

  explicit CentroidDecomposition(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : graph(graph) {
    const int n = graph.size();
    parent.assign(n, -1);
    g.resize(n);
    is_alive.assign(n, true);
    subtree.resize(n);
    root = build(0);
  }

 private:
  std::vector<bool> is_alive;
  std::vector<int> subtree;
  const std::vector<std::vector<Edge<CostType>>> graph;

  int build(const int s) {
    const int centroid = search_centroid(-1, s, calc_subtree(-1, s) / 2);
    is_alive[centroid] = false;
    for (const int e : graph[centroid]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (is_alive[e]) {
        const int child = build(e);
        g[centroid].emplace_back(child);
        parent[child] = centroid;
      }
    }
    is_alive[centroid] = true;
    return centroid;
  }

  int calc_subtree(const int par, const int ver) {
    subtree[ver] = 1;
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (e != par && is_alive[e]) {
        subtree[ver] += calc_subtree(ver, e);
      }
    }
    return subtree[ver];
  }

  int search_centroid(const int par, const int ver, const int half) const {
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (e != par && is_alive[e] && subtree[e] > half) {
        return search_centroid(ver, e, half);
      }
    }
    return ver;
  }
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_TREE_CENTROID_DECOMPOSITION_HPP_

#line 1 "include/emthrm/graph/tree/centroid_decomposition.hpp"



#include <ranges>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 8 "include/emthrm/graph/tree/centroid_decomposition.hpp"

namespace emthrm {

template <typename CostType>
struct CentroidDecomposition {
  int root;
  std::vector<int> parent;
  std::vector<std::vector<int>> g;

  explicit CentroidDecomposition(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : graph(graph) {
    const int n = graph.size();
    parent.assign(n, -1);
    g.resize(n);
    is_alive.assign(n, true);
    subtree.resize(n);
    root = build(0);
  }

 private:
  std::vector<bool> is_alive;
  std::vector<int> subtree;
  const std::vector<std::vector<Edge<CostType>>> graph;

  int build(const int s) {
    const int centroid = search_centroid(-1, s, calc_subtree(-1, s) / 2);
    is_alive[centroid] = false;
    for (const int e : graph[centroid]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (is_alive[e]) {
        const int child = build(e);
        g[centroid].emplace_back(child);
        parent[child] = centroid;
      }
    }
    is_alive[centroid] = true;
    return centroid;
  }

  int calc_subtree(const int par, const int ver) {
    subtree[ver] = 1;
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (e != par && is_alive[e]) {
        subtree[ver] += calc_subtree(ver, e);
      }
    }
    return subtree[ver];
  }

  int search_centroid(const int par, const int ver, const int half) const {
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (e != par && is_alive[e] && subtree[e] > half) {
        return search_centroid(ver, e, half);
      }
    }
    return ver;
  }
};

}  // namespace emthrm

Back to top page