Centroid Decomposition
(src/tree/CentroidDecomposition.hpp)

• View this file on GitHub
• Last update: 2024-03-31 18:08:00+09:00
• Include: #include "src/tree/CentroidDecomposition.hpp"

概要

木の重心分解を扱う．

メンバ関数	効果	時間計算量
CentroidDecomposition(n)	頂点数 $n$ の木として初期化する．	$\mathrm{O}(n)$
add_edge(u, v)	辺 $(u, v)$ を追加する．	$\mathrm{O}(1)$
build()	重心分解を構築する（後述）	$\mathrm{O}(n \log n)$

木の重心とは，その頂点を取り除いて残るすべての部分木のうち最大のものの頂点数が最小になる頂点である． 特に嬉しいのは，重心を取り除いて残るすべての部分木の頂点数がもとの木の頂点数の半分以下になっているという性質で，これにより再帰の深さは $\mathrm{O}(\log n)$ で抑えられる． 各深さ帯においての処理に $\mathrm{O}(n)$ かけてもよく，現在の部分木の頂点を全探索するといったことも行える． このためパスの数え上げ等の問題によく用いられる手法である．

メンバ関数 build() はもとの木を重心分解していく過程における重心を dfs-order に列挙する． これをもとにまた別に重心を潰しながら探索していくのが良い．

出題例

• COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred) E. Eye-Pleasing City Park Tour
  • 頂点に重みがついた，距離 $k$ 以下のパスの重みの総和の数え上げ．
• AtCoder Regular Contest 087 F - Squirrel Migration
  • 直接重心分解を用いる訳ではないが重心の性質を利用する．
• Starters 83 Beauty Sum

Verified with

• test/yosupo/frequency_table_of_tree_distance.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>

struct CentroidDecomposition {
    std::vector<std::vector<int>> G;

    CentroidDecomposition(int n) : G(n), n(n), sub(n), is_centroid(n) {}

    void add_edge(int u, int v) {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    std::vector<int> build(int x = 0) {
        centroids.clear();
        fill(is_centroid.begin(), is_centroid.end(), false);
        centroid_decomposition(x);
        return centroids;
    }

  private:
    int n;
    std::vector<int> sub, centroids;
    std::vector<bool> is_centroid;

    int dfs_sz(int v, int p) {
        sub[v] = 1;
        for (int& u : G[v]) {
            if (u == p || is_centroid[u]) continue;
            sub[v] += dfs_sz(u, v);
        }
        return sub[v];
    }

    int dfs_search_centroid(int v, int p, int mid) {
        for (int& u : G[v]) {
            if (u == p || is_centroid[u]) continue;
            if (sub[u] > mid) return dfs_search_centroid(u, v, mid);
        }
        return v;
    }

    void centroid_decomposition(int r) {
        int centroid = dfs_search_centroid(r, -1, dfs_sz(r, -1) / 2);
        centroids.emplace_back(centroid);
        is_centroid[centroid] = true;
        for (int& ch : G[centroid]) {
            if (is_centroid[ch]) continue;
            centroid_decomposition(ch);
        }
    }
};

#line 2 "src/tree/CentroidDecomposition.hpp"
#include <cassert>
#include <vector>

struct CentroidDecomposition {
    std::vector<std::vector<int>> G;

    CentroidDecomposition(int n) : G(n), n(n), sub(n), is_centroid(n) {}

    void add_edge(int u, int v) {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    std::vector<int> build(int x = 0) {
        centroids.clear();
        fill(is_centroid.begin(), is_centroid.end(), false);
        centroid_decomposition(x);
        return centroids;
    }

  private:
    int n;
    std::vector<int> sub, centroids;
    std::vector<bool> is_centroid;

    int dfs_sz(int v, int p) {
        sub[v] = 1;
        for (int& u : G[v]) {
            if (u == p || is_centroid[u]) continue;
            sub[v] += dfs_sz(u, v);
        }
        return sub[v];
    }

    int dfs_search_centroid(int v, int p, int mid) {
        for (int& u : G[v]) {
            if (u == p || is_centroid[u]) continue;
            if (sub[u] > mid) return dfs_search_centroid(u, v, mid);
        }
        return v;
    }

    void centroid_decomposition(int r) {
        int centroid = dfs_search_centroid(r, -1, dfs_sz(r, -1) / 2);
        centroids.emplace_back(centroid);
        is_centroid[centroid] = true;
        for (int& ch : G[centroid]) {
            if (is_centroid[ch]) continue;
            centroid_decomposition(ch);
        }
    }
};

Back to top page