Centroid Decomposition
(tree/centroid_decomposition.hpp)

• View this file on GitHub
• Last update: 2024-03-12 17:35:15+09:00
• Include: #include "tree/centroid_decomposition.hpp"

説明

重心分解を行い、重心分解後の各木に対して関数 $f$ を適用する。下記のように使用する。ここで MODE の値によって指定した MODE で実行される。

centroid_decomposition<MODE>(tree, f)

共通の仕様

重心分解後の木は $par$ で与えられ、頂点 $v$ の親が $par[v]$ となっている。また、重心分解後の頂点 $v$ の元の木の頂点番号は $vs[v]$ となっている。

MODE 0

通常の重心分解をする。下記のような関数 $f$ を重心分解後の木について適用する。

f(const std::vector<int> &par, const std::vector<int> &vs, const std::vector<int> &index_ptr)

重心、重心の部分木をそれぞれ異なる色で塗る。ここで、重心の色は $0$ である。 色 $c$ の頂点数は $(index\_ptr[c+1] - index\_ptr[c])$ 個であり、頂点番号は $index\_ptr[c]$ から $index\_ptr[c+1]$ となっている。

MODE 1

$\frac{1}{3}$ 重心分解を行う。下記のような関数 $f$ を重心分解後の木について適用する。パスの長さが $1$ のものについては処理しないため別途処理が必要。

f(const std::vector<int> &par, const std::vector<int> &vs, int n0, int n1)

重心の部分木を $2$ 色に塗り分ける。ここで、頂点 $0$ が重心、 $[1, 1 + n0)$ が色 $0$ 、 $[1 + n0, 1 + n0 + n2)$ が色 $1$ となっている。

辺の本数がだいたい $\frac{1}{2}$ になるように分割しているため、再帰の深さが $O(log{N})$ となる。一方で、各頂点の表れる回数は抑えられていないため注意。（スターグラフなど）

MODE 2

$\frac{1}{3}$ 重心分解を行う。下記のような関数 $f$ を重心分解後の木について適用する。

f(const std::vector<int> &par, const std::vector<int> &vs, const std::vector<int> &color)

頂点には $virtual$ 属性と $real$ 属性があり、 $color[v] = -1$ のとき頂点 $v$ は $virtual$ 属性である。頂点は $2$ 色で塗られており、 $color$ に色が格納されている。

各頂点の $real$ 属性で表れる回数が $O(\log{N})$ となる。始点を固定した場合のパスの処理などで活用できる。なお、 $virtual$ 属性で表れる回数は抑えられていないため注意。

reference

• 重心分解・1/3重心分解のお絵描き
• Theoretically Faster HLD and Centroid Decomposition

Required by

• Contour Query on Tree (tree/contour_query_on_tree.hpp)
• Contour Query on Tree (Weighted) (tree/contour_query_on_weighted_tree.hpp)

Verified with

• test/tree/Frequency_Table_of_Tree_Distance_MODE_0.test.cpp
• test/tree/Frequency_Table_of_Tree_Distance_MODE_1.test.cpp
• test/tree/Frequency_Table_of_Tree_Distance_MODE_2.test.cpp
• test/tree/Vertex_Add_Range_Contour_Sum_on_Tree.test.cpp
• test/tree/Vertex_Add_Range_Contour_Sum_on_Tree_2.test.cpp
• test/tree/Vertex_Get_Range_Contour_Add_on_Tree.test.cpp
• test/yuki/yuki_1038.test.cpp
• test/yuki/yuki_1796.test.cpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <ranges>
#include <vector>

namespace ebi {

namespace internal {

template <class F>
void centroid_decomposition_dfs_naive(const std::vector<int> &par,
                                      const std::vector<int> &original_vs,
                                      F f) {
    const int n = (int)par.size();
    assert(par.size() == original_vs.size());
    int center = -1;
    std::vector<int> sz(n, 1);
    for (const int v : std::views::iota(0, n) | std::views::reverse) {
        if (sz[v] >= (n + 1) / 2) {
            center = v;
            break;
        }
        sz[par[v]] += sz[v];
    }
    std::vector<int> color(n, -1);
    std::vector<int> vs = {center};
    color[center] = 0;
    int c = 1;
    for (const int v : std::views::iota(1, n)) {
        if (par[v] == center) {
            vs.emplace_back(v);
            color[v] = c++;
        }
    }
    if (center > 0) {
        for (int v = par[center]; v != -1; v = par[v]) {
            vs.emplace_back(v);
            color[v] = c;
        }
        c++;
    }
    for (const int v : std::views::iota(0, n)) {
        if (color[v] == -1) {
            vs.emplace_back(v);
            color[v] = color[par[v]];
        }
    }
    std::vector<int> index_ptr(c + 1, 0);
    for (const int v : std::views::iota(0, n)) {
        index_ptr[color[v] + 1]++;
    }
    for (const int i : std::views::iota(0, c)) {
        index_ptr[i + 1] += index_ptr[i];
    }
    auto counter = index_ptr;
    std::vector<int> ord(n);
    for (auto v : vs) {
        ord[counter[color[v]]++] = v;
    }
    std::vector<int> relabel(n);
    for (const int v : std::views::iota(0, n)) {
        relabel[ord[v]] = v;
    }
    std::vector<int> original_vs2(n);
    for (const int v : std::views::iota(0, n)) {
        original_vs2[relabel[v]] = original_vs[v];
    }
    std::vector<int> relabel_par(n, -1);
    for (int v : std::views::iota(1, n)) {
        int a = relabel[v];
        int b = relabel[par[v]];
        if (a > b) std::swap(a, b);
        relabel_par[b] = a;
    }
    f(relabel_par, original_vs2, index_ptr);
    for (const int i : std::views::iota(1, c)) {
        int l = index_ptr[i], r = index_ptr[i + 1];
        std::vector<int> par1(r - l, -1);
        std::vector<int> original_vs1(r - l, -1);
        for (int v : std::views::iota(l, r)) {
            par1[v - l] = (relabel_par[v] == 0 ? -1 : relabel_par[v] - l);
            original_vs1[v - l] = original_vs2[v];
        }
        centroid_decomposition_dfs_naive(par1, original_vs1, f);
    }
    return;
}

template <class F>
void one_third_centroid_decomposition(const std::vector<int> &par,
                                      const std::vector<int> &original_vs,
                                      F f) {
    const int n = (int)par.size();
    assert(n > 1);
    if (n == 2) return;
    int center = -1;
    std::vector<int> sz(n, 1);

    for (const int v : std::views::iota(0, n) | std::views::reverse) {
        if (sz[v] >= (n + 1) / 2) {
            center = v;
            break;
        }
        sz[par[v]] += sz[v];
    }

    std::vector<int> color(n, -1);
    std::vector<int> ord(n, -1);
    ord[center] = 0;
    int t = 1;
    int red = n - sz[center];
    for (int v = par[center]; v != -1; v = par[v]) {
        ord[v] = t++;
        color[v] = 0;
    }
    for (const int v : std::views::iota(1, n)) {
        if (par[v] == center && 3 * (red + sz[v]) <= 2 * (n - 1)) {
            red += sz[v];
            ord[v] = t++;
            color[v] = 0;
        }
    }
    for (const int v : std::views::iota(1, n)) {
        if (v != center && color[v] == -1 && color[par[v]] == 0) {
            ord[v] = t++;
            color[v] = 0;
        }
    }
    const int n0 = t - 1;
    for (const int v : std::views::iota(1, n)) {
        if (v != center && color[v] == -1) {
            ord[v] = t++;
            color[v] = 1;
        }
    }
    assert(t == n);
    const int n1 = n - 1 - n0;
    std::vector<int> par0(n0 + 1, -1), par1(n1 + 1, -1), par2(n, -1);
    std::vector<int> original_vs0(n0 + 1), original_vs1(n1 + 1),
        original_vs2(n);
    for (const int i : std::views::iota(0, n)) {
        int v = ord[i];
        original_vs2[v] = original_vs[i];
        if (color[i] != 1) {
            original_vs0[v] = original_vs[i];
        }
        if (color[i] != 0) {
            int idx = std::max(v - n0, 0);
            original_vs1[idx] = original_vs[i];
        }
    }
    for (const int v : std::views::iota(1, n)) {
        int a = ord[v], b = ord[par[v]];
        if (a > b) std::swap(a, b);
        par2[b] = a;
        if (color[v] != 1 && color[par[v]] != 1) {
            par0[b] = a;
        }
        if (color[v] != 0 && color[par[v]] != 0) {
            par1[b - n0] = std::max(a - n0, 0);
        }
    }
    f(par2, original_vs2, n0, n1);
    one_third_centroid_decomposition(par0, original_vs0, f);
    one_third_centroid_decomposition(par1, original_vs1, f);
    return;
}

template <class F>
void one_third_centroid_decomposition_virtual_real(
    const std::vector<int> &par, const std::vector<int> &original_vs,
    const std::vector<int> &is_real, F f) {
    const int n = (int)par.size();
    assert(n > 1);
    if (n == 2) {
        if (is_real[0] && is_real[1]) {
            f(par, original_vs, {0, 1});
        }
        return;
    }
    int center = -1;
    std::vector<int> sz(n, 1);

    for (const int v : std::views::iota(0, n) | std::views::reverse) {
        if (sz[v] >= (n + 1) / 2) {
            center = v;
            break;
        }
        sz[par[v]] += sz[v];
    }

    std::vector<int> color(n, -1);
    std::vector<int> ord(n, -1);
    ord[center] = 0;
    int t = 1;
    int red = n - sz[center];
    for (int v = par[center]; v != -1; v = par[v]) {
        ord[v] = t++;
        color[v] = 0;
    }
    for (const int v : std::views::iota(1, n)) {
        if (par[v] == center && 3 * (red + sz[v]) <= 2 * (n - 1)) {
            red += sz[v];
            ord[v] = t++;
            color[v] = 0;
        }
    }
    for (const int v : std::views::iota(1, n)) {
        if (v != center && color[v] == -1 && color[par[v]] == 0) {
            ord[v] = t++;
            color[v] = 0;
        }
    }
    const int n0 = t - 1;
    for (const int v : std::views::iota(1, n)) {
        if (v != center && color[v] == -1) {
            ord[v] = t++;
            color[v] = 1;
        }
    }
    assert(t == n);
    const int n1 = n - 1 - n0;
    std::vector<int> par0(n0 + 1, -1), par1(n1 + 1, -1), par2(n, -1);
    std::vector<int> original_vs0(n0 + 1), original_vs1(n1 + 1),
        original_vs2(n);
    std::vector<int> is_real0(n0 + 1), is_real1(n1 + 1), is_real2(n);
    for (const int i : std::views::iota(0, n)) {
        int v = ord[i];
        original_vs2[v] = original_vs[i];
        is_real2[v] = is_real[i];
        if (color[i] != 1) {
            original_vs0[v] = original_vs[i];
            is_real0[v] = is_real[i];
        }
        if (color[i] != 0) {
            int idx = std::max(v - n0, 0);
            original_vs1[idx] = original_vs[i];
            is_real1[idx] = is_real[i];
        }
    }
    for (const int v : std::views::iota(1, n)) {
        int a = ord[v], b = ord[par[v]];
        if (a > b) std::swap(a, b);
        par2[b] = a;
        if (color[v] != 1 && color[par[v]] != 1) {
            par0[b] = a;
        }
        if (color[v] != 0 && color[par[v]] != 0) {
            par1[b - n0] = std::max(a - n0, 0);
        }
    }
    if (is_real[center]) {
        color.assign(n, -1);
        color[0] = 0;
        for (const int v : std::views::iota(1, n)) {
            if (is_real2[v]) color[v] = 1;
        }
        f(par2, original_vs2, color);
        is_real0[0] = is_real1[0] = is_real2[0] = 0;
    }
    color.assign(n, -1);
    for (const int v : std::views::iota(1, n)) {
        if (is_real2[v]) {
            color[v] = int(v > n0);
        }
    }
    f(par2, original_vs2, color);
    one_third_centroid_decomposition_virtual_real(par0, original_vs0, is_real0,
                                                  f);
    one_third_centroid_decomposition_virtual_real(par1, original_vs1, is_real1,
                                                  f);
    return;
}

}  // namespace internal

template <int MODE, class T, class F>
void centroid_decomposition(const Graph<T> &tree, F f) {
    int n = (int)tree.size();
    if (n == 1) return;
    std::vector<int> bfs_order(n), par(n, -1);
    bfs_order[0] = 0;
    int l = 0, r = 1;
    while (l < r) {
        int v = bfs_order[l++];
        for (auto e : tree[v]) {
            int nv = e.to;
            if (nv == par[v]) continue;
            bfs_order[r++] = nv;
            par[nv] = v;
        }
    }
    assert(l == n && r == n);
    {
        std::vector<int> relabel(n);
        for (int i : std::views::iota(0, n)) {
            relabel[bfs_order[i]] = i;
        }
        std::vector<int> relabel_par(n, -1);
        for (int i : std::views::iota(1, n)) {
            relabel_par[relabel[i]] = relabel[par[i]];
        }
        std::swap(par, relabel_par);
    }
    static_assert(MODE == 0 || MODE == 1 || MODE == 2);
    if constexpr (MODE == 0) {
        internal::centroid_decomposition_dfs_naive(par, bfs_order, f);
    } else if constexpr (MODE == 1) {
        internal::one_third_centroid_decomposition(par, bfs_order, f);
    } else {
        internal::one_third_centroid_decomposition_virtual_real(
            par, bfs_order, std::vector<int>(n, 1), f);
    }
}

}  // namespace ebi

#line 2 "tree/centroid_decomposition.hpp"

#include <algorithm>
#include <cassert>
#include <ranges>
#include <vector>

namespace ebi {

namespace internal {

template <class F>
void centroid_decomposition_dfs_naive(const std::vector<int> &par,
                                      const std::vector<int> &original_vs,
                                      F f) {
    const int n = (int)par.size();
    assert(par.size() == original_vs.size());
    int center = -1;
    std::vector<int> sz(n, 1);
    for (const int v : std::views::iota(0, n) | std::views::reverse) {
        if (sz[v] >= (n + 1) / 2) {
            center = v;
            break;
        }
        sz[par[v]] += sz[v];
    }
    std::vector<int> color(n, -1);
    std::vector<int> vs = {center};
    color[center] = 0;
    int c = 1;
    for (const int v : std::views::iota(1, n)) {
        if (par[v] == center) {
            vs.emplace_back(v);
            color[v] = c++;
        }
    }
    if (center > 0) {
        for (int v = par[center]; v != -1; v = par[v]) {
            vs.emplace_back(v);
            color[v] = c;
        }
        c++;
    }
    for (const int v : std::views::iota(0, n)) {
        if (color[v] == -1) {
            vs.emplace_back(v);
            color[v] = color[par[v]];
        }
    }
    std::vector<int> index_ptr(c + 1, 0);
    for (const int v : std::views::iota(0, n)) {
        index_ptr[color[v] + 1]++;
    }
    for (const int i : std::views::iota(0, c)) {
        index_ptr[i + 1] += index_ptr[i];
    }
    auto counter = index_ptr;
    std::vector<int> ord(n);
    for (auto v : vs) {
        ord[counter[color[v]]++] = v;
    }
    std::vector<int> relabel(n);
    for (const int v : std::views::iota(0, n)) {
        relabel[ord[v]] = v;
    }
    std::vector<int> original_vs2(n);
    for (const int v : std::views::iota(0, n)) {
        original_vs2[relabel[v]] = original_vs[v];
    }
    std::vector<int> relabel_par(n, -1);
    for (int v : std::views::iota(1, n)) {
        int a = relabel[v];
        int b = relabel[par[v]];
        if (a > b) std::swap(a, b);
        relabel_par[b] = a;
    }
    f(relabel_par, original_vs2, index_ptr);
    for (const int i : std::views::iota(1, c)) {
        int l = index_ptr[i], r = index_ptr[i + 1];
        std::vector<int> par1(r - l, -1);
        std::vector<int> original_vs1(r - l, -1);
        for (int v : std::views::iota(l, r)) {
            par1[v - l] = (relabel_par[v] == 0 ? -1 : relabel_par[v] - l);
            original_vs1[v - l] = original_vs2[v];
        }
        centroid_decomposition_dfs_naive(par1, original_vs1, f);
    }
    return;
}

template <class F>
void one_third_centroid_decomposition(const std::vector<int> &par,
                                      const std::vector<int> &original_vs,
                                      F f) {
    const int n = (int)par.size();
    assert(n > 1);
    if (n == 2) return;
    int center = -1;
    std::vector<int> sz(n, 1);

    for (const int v : std::views::iota(0, n) | std::views::reverse) {
        if (sz[v] >= (n + 1) / 2) {
            center = v;
            break;
        }
        sz[par[v]] += sz[v];
    }

    std::vector<int> color(n, -1);
    std::vector<int> ord(n, -1);
    ord[center] = 0;
    int t = 1;
    int red = n - sz[center];
    for (int v = par[center]; v != -1; v = par[v]) {
        ord[v] = t++;
        color[v] = 0;
    }
    for (const int v : std::views::iota(1, n)) {
        if (par[v] == center && 3 * (red + sz[v]) <= 2 * (n - 1)) {
            red += sz[v];
            ord[v] = t++;
            color[v] = 0;
        }
    }
    for (const int v : std::views::iota(1, n)) {
        if (v != center && color[v] == -1 && color[par[v]] == 0) {
            ord[v] = t++;
            color[v] = 0;
        }
    }
    const int n0 = t - 1;
    for (const int v : std::views::iota(1, n)) {
        if (v != center && color[v] == -1) {
            ord[v] = t++;
            color[v] = 1;
        }
    }
    assert(t == n);
    const int n1 = n - 1 - n0;
    std::vector<int> par0(n0 + 1, -1), par1(n1 + 1, -1), par2(n, -1);
    std::vector<int> original_vs0(n0 + 1), original_vs1(n1 + 1),
        original_vs2(n);
    for (const int i : std::views::iota(0, n)) {
        int v = ord[i];
        original_vs2[v] = original_vs[i];
        if (color[i] != 1) {
            original_vs0[v] = original_vs[i];
        }
        if (color[i] != 0) {
            int idx = std::max(v - n0, 0);
            original_vs1[idx] = original_vs[i];
        }
    }
    for (const int v : std::views::iota(1, n)) {
        int a = ord[v], b = ord[par[v]];
        if (a > b) std::swap(a, b);
        par2[b] = a;
        if (color[v] != 1 && color[par[v]] != 1) {
            par0[b] = a;
        }
        if (color[v] != 0 && color[par[v]] != 0) {
            par1[b - n0] = std::max(a - n0, 0);
        }
    }
    f(par2, original_vs2, n0, n1);
    one_third_centroid_decomposition(par0, original_vs0, f);
    one_third_centroid_decomposition(par1, original_vs1, f);
    return;
}

template <class F>
void one_third_centroid_decomposition_virtual_real(
    const std::vector<int> &par, const std::vector<int> &original_vs,
    const std::vector<int> &is_real, F f) {
    const int n = (int)par.size();
    assert(n > 1);
    if (n == 2) {
        if (is_real[0] && is_real[1]) {
            f(par, original_vs, {0, 1});
        }
        return;
    }
    int center = -1;
    std::vector<int> sz(n, 1);

    for (const int v : std::views::iota(0, n) | std::views::reverse) {
        if (sz[v] >= (n + 1) / 2) {
            center = v;
            break;
        }
        sz[par[v]] += sz[v];
    }

    std::vector<int> color(n, -1);
    std::vector<int> ord(n, -1);
    ord[center] = 0;
    int t = 1;
    int red = n - sz[center];
    for (int v = par[center]; v != -1; v = par[v]) {
        ord[v] = t++;
        color[v] = 0;
    }
    for (const int v : std::views::iota(1, n)) {
        if (par[v] == center && 3 * (red + sz[v]) <= 2 * (n - 1)) {
            red += sz[v];
            ord[v] = t++;
            color[v] = 0;
        }
    }
    for (const int v : std::views::iota(1, n)) {
        if (v != center && color[v] == -1 && color[par[v]] == 0) {
            ord[v] = t++;
            color[v] = 0;
        }
    }
    const int n0 = t - 1;
    for (const int v : std::views::iota(1, n)) {
        if (v != center && color[v] == -1) {
            ord[v] = t++;
            color[v] = 1;
        }
    }
    assert(t == n);
    const int n1 = n - 1 - n0;
    std::vector<int> par0(n0 + 1, -1), par1(n1 + 1, -1), par2(n, -1);
    std::vector<int> original_vs0(n0 + 1), original_vs1(n1 + 1),
        original_vs2(n);
    std::vector<int> is_real0(n0 + 1), is_real1(n1 + 1), is_real2(n);
    for (const int i : std::views::iota(0, n)) {
        int v = ord[i];
        original_vs2[v] = original_vs[i];
        is_real2[v] = is_real[i];
        if (color[i] != 1) {
            original_vs0[v] = original_vs[i];
            is_real0[v] = is_real[i];
        }
        if (color[i] != 0) {
            int idx = std::max(v - n0, 0);
            original_vs1[idx] = original_vs[i];
            is_real1[idx] = is_real[i];
        }
    }
    for (const int v : std::views::iota(1, n)) {
        int a = ord[v], b = ord[par[v]];
        if (a > b) std::swap(a, b);
        par2[b] = a;
        if (color[v] != 1 && color[par[v]] != 1) {
            par0[b] = a;
        }
        if (color[v] != 0 && color[par[v]] != 0) {
            par1[b - n0] = std::max(a - n0, 0);
        }
    }
    if (is_real[center]) {
        color.assign(n, -1);
        color[0] = 0;
        for (const int v : std::views::iota(1, n)) {
            if (is_real2[v]) color[v] = 1;
        }
        f(par2, original_vs2, color);
        is_real0[0] = is_real1[0] = is_real2[0] = 0;
    }
    color.assign(n, -1);
    for (const int v : std::views::iota(1, n)) {
        if (is_real2[v]) {
            color[v] = int(v > n0);
        }
    }
    f(par2, original_vs2, color);
    one_third_centroid_decomposition_virtual_real(par0, original_vs0, is_real0,
                                                  f);
    one_third_centroid_decomposition_virtual_real(par1, original_vs1, is_real1,
                                                  f);
    return;
}

}  // namespace internal

template <int MODE, class T, class F>
void centroid_decomposition(const Graph<T> &tree, F f) {
    int n = (int)tree.size();
    if (n == 1) return;
    std::vector<int> bfs_order(n), par(n, -1);
    bfs_order[0] = 0;
    int l = 0, r = 1;
    while (l < r) {
        int v = bfs_order[l++];
        for (auto e : tree[v]) {
            int nv = e.to;
            if (nv == par[v]) continue;
            bfs_order[r++] = nv;
            par[nv] = v;
        }
    }
    assert(l == n && r == n);
    {
        std::vector<int> relabel(n);
        for (int i : std::views::iota(0, n)) {
            relabel[bfs_order[i]] = i;
        }
        std::vector<int> relabel_par(n, -1);
        for (int i : std::views::iota(1, n)) {
            relabel_par[relabel[i]] = relabel[par[i]];
        }
        std::swap(par, relabel_par);
    }
    static_assert(MODE == 0 || MODE == 1 || MODE == 2);
    if constexpr (MODE == 0) {
        internal::centroid_decomposition_dfs_naive(par, bfs_order, f);
    } else if constexpr (MODE == 1) {
        internal::one_third_centroid_decomposition(par, bfs_order, f);
    } else {
        internal::one_third_centroid_decomposition_virtual_real(
            par, bfs_order, std::vector<int>(n, 1), f);
    }
}

}  // namespace ebi

Back to top page