Centroid Decomposition
(tree/centroid_decomposition.hpp)

• View this file on GitHub
• Last update: 2024-01-07 23:25:49+09:00
• Include: #include "tree/centroid_decomposition.hpp"

Description

木の重心とは，木の頂点であって，その頂点を除いてできる森の各連結成分のサイズがもとの木の半分以下になるようなものである．

木の重心による分割を再帰的に行う．木上の分割統治に用いる．

Operations

• tuple<vector<int>, vector<int>, vector<int>> centroid_decomposition(vector<vector<int>> G)
  • 木 $G$ の隣接リストが与えられたとき，3つ組 (level, sz, par) を返す．
    • level: $G$ を重心分解したときの各頂点のレベル (何回目の分割でそれが重心となるか)
    • sz: 各頂点が重心となるときにそれが含まれる部分木のサイズ
    • par: 各頂点が重心となる直前に属していた部分木の重心
  • 時間計算量: $O(n\log n)$

Reference

• ツリーの重心分解 (木の重心分解) の図解 - Qiita

Required by

• Range Contour Aggregation (tree/range_contour_aggregation.hpp)

Verified with

• test/yosupo/frequency_table_of_tree_distance.test.cpp
• test/yosupo/vertex_add_range_contour_sum_on_tree.test.cpp

Code

#pragma once
#include <tuple>
#include <vector>

std::tuple<std::vector<int>, std::vector<int>, std::vector<int>>
centroid_decomposition(const std::vector<std::vector<int>>& G) {
    const int N = G.size();
    std::vector<int> sz(N), level(N, -1), sz_comp(N), par(N);

    auto dfs_size = [&](auto& dfs_size, int v, int p) -> int {
        sz[v] = 1;
        for (int c : G[v]) {
            if (c != p && level[c] == -1) sz[v] += dfs_size(dfs_size, c, v);
        }
        return sz[v];
    };

    auto dfs_centroid = [&](auto& dfs_centroid, int v, int p, int n) -> int {
        for (int c : G[v]) {
            if (c != p && level[c] == -1 && sz[c] > n / 2)
                return dfs_centroid(dfs_centroid, c, v, n);
        }
        return v;
    };

    auto decompose = [&](auto& decompose, int v, int k, int p) -> void {
        int n = dfs_size(dfs_size, v, -1);
        int s = dfs_centroid(dfs_centroid, v, -1, n);
        level[s] = k;
        sz_comp[s] = n;
        par[s] = p;
        for (int c : G[s]) {
            if (level[c] == -1) decompose(decompose, c, k + 1, s);
        }
    };

    decompose(decompose, 0, 0, -1);
    return {level, sz_comp, par};
}

#line 2 "tree/centroid_decomposition.hpp"
#include <tuple>
#include <vector>

std::tuple<std::vector<int>, std::vector<int>, std::vector<int>>
centroid_decomposition(const std::vector<std::vector<int>>& G) {
    const int N = G.size();
    std::vector<int> sz(N), level(N, -1), sz_comp(N), par(N);

    auto dfs_size = [&](auto& dfs_size, int v, int p) -> int {
        sz[v] = 1;
        for (int c : G[v]) {
            if (c != p && level[c] == -1) sz[v] += dfs_size(dfs_size, c, v);
        }
        return sz[v];
    };

    auto dfs_centroid = [&](auto& dfs_centroid, int v, int p, int n) -> int {
        for (int c : G[v]) {
            if (c != p && level[c] == -1 && sz[c] > n / 2)
                return dfs_centroid(dfs_centroid, c, v, n);
        }
        return v;
    };

    auto decompose = [&](auto& decompose, int v, int k, int p) -> void {
        int n = dfs_size(dfs_size, v, -1);
        int s = dfs_centroid(dfs_centroid, v, -1, n);
        level[s] = k;
        sz_comp[s] = n;
        par[s] = p;
        for (int c : G[s]) {
            if (level[c] == -1) decompose(decompose, c, k + 1, s);
        }
    };

    decompose(decompose, 0, 0, -1);
    return {level, sz_comp, par};
}

Back to top page