Centroid Decomposition
(graph/tree/centroid_decomposition.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/tree/centroid_decomposition.hpp"

Overview

m1une::tree::CentroidDecomposition<T> builds the centroid tree of an undirected tree. It also supports forests; each connected component contributes one centroid-tree root.

The input uses m1une::graph::Graph<T> and should be built with add_edge. Inactive edges are ignored.

Public Members

Member	Type	Description
`n`	`int`	Number of vertices in the source graph.
`parent`	`std::vector<int>`	Parent in the centroid tree, or `-1` for a centroid root.
`depth`	`std::vector<int>`	Depth in the centroid tree.
`order`	`std::vector<int>`	Centroids in decomposition order.
`roots`	`std::vector<int>`	Centroid roots, one per connected component.
`children`	`std::vector<std::vector<int>>`	Children in the centroid tree.

Methods

Method	Description	Complexity
`CentroidDecomposition(g)`	Builds the centroid decomposition.	$O(N \log N)$
`void build(g)`	Rebuilds the decomposition.	$O(N \log N)$
`int size()`	Returns `n`.	$O(1)$
`bool empty()`	Returns whether `n == 0`.	$O(1)$
`int root()`	Returns the first centroid root, or `-1`.	$O(1)$

How to Use It in Problems

Centroid decomposition is useful when updates or queries are about distances to many vertices on the original tree.

Typical examples:

Turn a vertex on/off and query the nearest active vertex.
Count active vertices within distance K.
Add a value to one vertex and query a distance-dependent aggregate.
Count pairs of vertices whose distance satisfies a condition.

The key idea is that every original vertex has only $O(\log N)$ ancestors in the centroid tree. For a vertex v, climb:

for (int c = v; c != -1; c = cd.parent[c]) {
    // c is a centroid ancestor of v, including v if v became a centroid.
}

If a query at v can be answered by combining information stored at each centroid ancestor c, then each operation becomes $O(\log N)$ or $O(\log^2 N)$ depending on how distances are obtained.

For repeated operations, precompute the centroid ancestors and their original tree distances:

m1une::tree::RootedTree<int> tree(g, 0);
m1une::tree::CentroidDecomposition<int> cd(g);

std::vector<std::vector<std::pair<int, int>>> centroid_path(n);
for (int v = 0; v < n; v++) {
    for (int c = v; c != -1; c = cd.parent[c]) {
        centroid_path[v].push_back({c, tree.dist_edges(v, c)});
    }
}

Now centroid_path[v] contains all relevant centroids for v, with distances measured on the original tree.

Dynamic Nearest Active Vertex

This is the most common centroid decomposition pattern.

Maintain best[c]: the minimum original-tree distance from centroid c to any active vertex.

Activating a vertex v updates all centroid ancestors of v:

const int INF = 1 << 30;
std::vector<int> best(n, INF);

auto activate = [&](int v) {
    for (auto [c, d] : centroid_path[v]) {
        best[c] = std::min(best[c], d);
    }
};

To query the nearest active vertex to v, try every centroid ancestor c. Any active vertex x is represented at the first centroid that separates the path between v and x, so checking all centroid ancestors is enough.

auto query = [&](int v) {
    int ans = INF;
    for (auto [c, d] : centroid_path[v]) {
        ans = std::min(ans, best[c] + d);
    }
    return ans == INF ? -1 : ans;
};

Each activate and query is $O(\log N)$ after the preprocessing above.

For toggling vertices off, best[c] is not enough because the removed vertex may have been the minimum. Use a std::multiset<int> for each centroid instead:

std::vector<std::multiset<int>> distances(n);
std::vector<char> active(n, false);

auto activate = [&](int v) {
    if (active[v]) return;
    active[v] = true;
    for (auto [c, d] : centroid_path[v]) distances[c].insert(d);
};

auto deactivate = [&](int v) {
    if (!active[v]) return;
    active[v] = false;
    for (auto [c, d] : centroid_path[v]) {
        auto it = distances[c].find(d);
        distances[c].erase(it);
    }
};

auto query = [&](int v) {
    int ans = INF;
    for (auto [c, d] : centroid_path[v]) {
        if (!distances[c].empty()) ans = std::min(ans, d + *distances[c].begin());
    }
    return ans == INF ? -1 : ans;
};

This gives $O(\log^2 N)$ updates because each multiset operation costs $O(\log N)$, and $O(\log N)$ queries.

Counting Vertices Within Distance K

For queries like “how many active vertices are within distance K from v”, store distances at each centroid in sorted containers.

The usual static version keeps:

all[c]: distances from centroid c to every active vertex whose centroid_path contains c.
sub[child]: distances from cd.parent[child] to active vertices that lie in that centroid-child side.

When inserting an active vertex x, climb its centroid ancestors while remembering the previous lower centroid:

int prev = -1;
for (auto [c, d] : centroid_path[x]) {
    all[c].push_back(d);
    if (prev != -1) sub[prev].push_back(d);
    prev = c;
}

After sorting these vectors, query from v by climbing the same way. Add the count from all[c] with distance at most K - dist(v, c), then subtract the count from the lower centroid side that also contains v.

This inclusion-exclusion pattern is the main trick for centroid decomposition counting problems.

Example

#include "graph/graph.hpp"
#include "graph/tree/centroid_decomposition.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<int> g(5);
    g.add_edge(0, 1);
    g.add_edge(1, 2);
    g.add_edge(1, 3);
    g.add_edge(3, 4);

    m1une::tree::CentroidDecomposition cd(g);
    std::cout << cd.root() << "\n";
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_TREE_CENTROID_DECOMPOSITION_HPP
#define M1UNE_TREE_CENTROID_DECOMPOSITION_HPP 1

#include <algorithm>
#include <vector>

#include "../graph.hpp"

namespace m1une {
namespace tree {

template <class T = int>
struct CentroidDecomposition {
    int n;
    std::vector<int> parent;
    std::vector<int> depth;
    std::vector<int> order;
    std::vector<int> roots;
    std::vector<std::vector<int>> children;

   private:
    std::vector<int> _subtree_size;
    std::vector<int> _work_parent;
    std::vector<char> _removed;

    void build_component(const m1une::graph::Graph<T>& g, int start, int p, int d) {
        std::vector<int> nodes;
        std::vector<int> stack = {start};
        _work_parent[start] = -2;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            nodes.push_back(v);
            for (const auto& e : g[v]) {
                if (!e.alive || _removed[e.to]) continue;
                if (_work_parent[e.to] != -1) continue;
                _work_parent[e.to] = v;
                stack.push_back(e.to);
            }
        }

        for (int v : nodes) _subtree_size[v] = 1;
        for (int i = int(nodes.size()) - 1; i >= 0; i--) {
            int v = nodes[i];
            if (_work_parent[v] >= 0) _subtree_size[_work_parent[v]] += _subtree_size[v];
        }

        int total = int(nodes.size());
        int centroid = start;
        int best = total + 1;
        for (int v : nodes) {
            int largest = total - _subtree_size[v];
            for (const auto& e : g[v]) {
                if (!e.alive || _removed[e.to]) continue;
                if (_work_parent[e.to] == v) largest = std::max(largest, _subtree_size[e.to]);
            }
            if (largest < best) {
                best = largest;
                centroid = v;
            }
        }

        for (int v : nodes) _work_parent[v] = -1;

        parent[centroid] = p;
        depth[centroid] = d;
        order.push_back(centroid);
        if (p == -1) {
            roots.push_back(centroid);
        } else {
            children[p].push_back(centroid);
        }
        _removed[centroid] = true;

        for (const auto& e : g[centroid]) {
            if (!e.alive || _removed[e.to]) continue;
            build_component(g, e.to, centroid, d + 1);
        }
    }

   public:
    CentroidDecomposition() : n(0) {}
    explicit CentroidDecomposition(const m1une::graph::Graph<T>& g) {
        build(g);
    }

    void build(const m1une::graph::Graph<T>& g) {
        n = g.size();
        parent.assign(n, -1);
        depth.assign(n, -1);
        order.clear();
        order.reserve(n);
        roots.clear();
        children.assign(n, {});
        _subtree_size.assign(n, 0);
        _work_parent.assign(n, -1);
        _removed.assign(n, false);

        for (int v = 0; v < n; v++) {
            if (depth[v] == -1) build_component(g, v, -1, 0);
        }
    }

    int size() const {
        return n;
    }

    bool empty() const {
        return n == 0;
    }

    int root() const {
        return roots.empty() ? -1 : roots[0];
    }
};

}  // namespace tree
}  // namespace m1une

#endif  // M1UNE_TREE_CENTROID_DECOMPOSITION_HPP

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



#include <algorithm>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#include <cassert>
#include <utility>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 8 "graph/tree/centroid_decomposition.hpp"

namespace m1une {
namespace tree {

template <class T = int>
struct CentroidDecomposition {
    int n;
    std::vector<int> parent;
    std::vector<int> depth;
    std::vector<int> order;
    std::vector<int> roots;
    std::vector<std::vector<int>> children;

   private:
    std::vector<int> _subtree_size;
    std::vector<int> _work_parent;
    std::vector<char> _removed;

    void build_component(const m1une::graph::Graph<T>& g, int start, int p, int d) {
        std::vector<int> nodes;
        std::vector<int> stack = {start};
        _work_parent[start] = -2;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            nodes.push_back(v);
            for (const auto& e : g[v]) {
                if (!e.alive || _removed[e.to]) continue;
                if (_work_parent[e.to] != -1) continue;
                _work_parent[e.to] = v;
                stack.push_back(e.to);
            }
        }

        for (int v : nodes) _subtree_size[v] = 1;
        for (int i = int(nodes.size()) - 1; i >= 0; i--) {
            int v = nodes[i];
            if (_work_parent[v] >= 0) _subtree_size[_work_parent[v]] += _subtree_size[v];
        }

        int total = int(nodes.size());
        int centroid = start;
        int best = total + 1;
        for (int v : nodes) {
            int largest = total - _subtree_size[v];
            for (const auto& e : g[v]) {
                if (!e.alive || _removed[e.to]) continue;
                if (_work_parent[e.to] == v) largest = std::max(largest, _subtree_size[e.to]);
            }
            if (largest < best) {
                best = largest;
                centroid = v;
            }
        }

        for (int v : nodes) _work_parent[v] = -1;

        parent[centroid] = p;
        depth[centroid] = d;
        order.push_back(centroid);
        if (p == -1) {
            roots.push_back(centroid);
        } else {
            children[p].push_back(centroid);
        }
        _removed[centroid] = true;

        for (const auto& e : g[centroid]) {
            if (!e.alive || _removed[e.to]) continue;
            build_component(g, e.to, centroid, d + 1);
        }
    }

   public:
    CentroidDecomposition() : n(0) {}
    explicit CentroidDecomposition(const m1une::graph::Graph<T>& g) {
        build(g);
    }

    void build(const m1une::graph::Graph<T>& g) {
        n = g.size();
        parent.assign(n, -1);
        depth.assign(n, -1);
        order.clear();
        order.reserve(n);
        roots.clear();
        children.assign(n, {});
        _subtree_size.assign(n, 0);
        _work_parent.assign(n, -1);
        _removed.assign(n, false);

        for (int v = 0; v < n; v++) {
            if (depth[v] == -1) build_component(g, v, -1, 0);
        }
    }

    int size() const {
        return n;
    }

    bool empty() const {
        return n == 0;
    }

    int root() const {
        return roots.empty() ? -1 : roots[0];
    }
};

}  // namespace tree
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Centroid Decomposition
(graph/tree/centroid_decomposition.hpp)

Overview

Public Members

Methods

How to Use It in Problems

Dynamic Nearest Active Vertex

Counting Vertices Within Distance K

Example

Depends on

Required by

Verified with

Code

Centroid Decomposition (graph/tree/centroid_decomposition.hpp)

Overview

Public Members

Methods

How to Use It in Problems

Dynamic Nearest Active Vertex

Counting Vertices Within Distance K

Example

Depends on

Required by

Verified with

Code

Centroid Decomposition
(graph/tree/centroid_decomposition.hpp)