Heavy Light Decomposition
(graph/tree/heavy_light_decomposition.hpp)

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

Overview

m1une::tree::HeavyLightDecomposition<T> decomposes a rooted tree into heavy paths. It maps every vertex to a position tin[v] in a base array, which lets path and subtree queries be answered by ordinary range data structures.

Use it with ds::Segtree, LazySegtree, or another range-query structure over the HLD order.

Inactive graph edges are ignored.

Path Segments

path_segments(u, v, edge) returns half-open base-array intervals covering the path from u to v.

Each segment has:

Field	Description
`l`, `r`	Half-open interval `[l, r)` in HLD order.
`reversed`	Whether the path direction traverses the interval from `r - 1` down to `l`.

When edge == false, vertex positions are covered. When edge == true, edge values are assumed to be stored at the child vertex position, so the LCA vertex is excluded.

Public Members

The input graph is first rooted at root. Then vertices are reordered into the HLD base array. If you build a segment tree with HLD, position tin[v] is the position corresponding to original vertex v.

For a connected tree, these arrays have size N, except order, which also has size N. The graph is expected to be a tree. If the graph is disconnected, only the component reachable from root gets valid HLD positions; vertices outside that component keep tin[v] == -1.

Member	Type	What is stored
`root`	`int`	The root used to orient the tree. It is `-1` for an empty graph.
`parent[v]`	`int`	The parent of `v` in the rooted original tree. `parent[root] == -1`.
`parent_edge[v]`	`int`	The graph edge id connecting `parent[v]` to `v`. It is `-1` for the root.
`depth[v]`	`int`	Number of edges from `root` to `v`.
`dist[v]`	`T`	Sum of edge costs from `root` to `v`. For an unweighted tree, this is the same as `depth[v]` if all costs are `1`.
`subtree_size[v]`	`int`	Number of vertices in the rooted subtree of `v`, including `v` itself.
`heavy[v]`	`int`	The child of `v` with the largest subtree. This child continues the same heavy path. It is `-1` if `v` has no children.
`head[v]`	`int`	The top vertex of the heavy path containing `v`. If `head[v] == head[u]`, then `u` and `v` are on the same heavy path.
`tin[v]`	`int`	Position of original vertex `v` in the HLD base array. This is the index to use in segment trees.
`tout[v]`	`int`	One past the end of the rooted subtree interval of `v` in HLD order. The subtree is `[tin[v], tout[v])`.
`order[i]`	`int`	The original vertex stored at HLD base-array position `i`. This is the inverse of `tin`: `order[tin[v]] == v`.

Important relationships:

Vertex v is stored at base-array index tin[v].
order[i] converts a base-array index back to the original vertex.
The rooted subtree of v occupies the contiguous interval [tin[v], tout[v]).
If you store edge values instead of vertex values, store the edge (parent[v], v) at tin[v]. The root has no parent edge.
Heavy paths are contiguous in the base array. That is why a path can be split into only $O(\log N)$ intervals.

For example, suppose the original tree is:

0
|- 1
|  |- 3
|  `- 4
`- 2

If 1 is chosen as the heavy child of 0, and 3 is chosen as the heavy child of 1, one possible HLD order is:

index: 0  1  2  3  4
order: 0  1  3  4  2

Then:

tin[0] = 0
tin[1] = 1
tin[3] = 2
tin[4] = 3
tin[2] = 4
head[0] = head[1] = head[3] = 0
head[4] = 4
head[2] = 2

The subtree of vertex 1 is vertices {1, 3, 4}, and it is stored contiguously as [tin[1], tout[1]) == [1, 4).

Methods

Method	Description	Complexity
`HeavyLightDecomposition(g, root)`	Builds HLD data.	$O(N)$
`void build(g, root)`	Rebuilds the structure.	$O(N)$
`int lca(u, v)`	Returns the lowest common ancestor.	$O(\log N)$
`int dist_edges(u, v)`	Returns the number of edges on the path.	$O(\log N)$
`T dist_cost(u, v)`	Returns the sum of edge costs on the path.	$O(\log N)$
`int kth_ancestor(v, k)`	Returns the `k`-th ancestor, or `-1`.	$O(\log N)$
`int jump(from, to, k)`	Returns the `k`-th vertex on the path, or `-1`.	$O(\log N)$
`std::pair<int, int> subtree_range(v, edge)`	Returns the subtree interval. With `edge=true`, excludes `v`.	$O(1)$
`std::vector<HldPathSegment> path_segments(u, v, edge)`	Returns path intervals in path order.	$O(\log N)$ intervals
`for_each_path(u, v, f, edge)`	Calls `f(l, r, reversed)` for each path segment.	$O(\log N)$ calls

Example

#include "ds/segtree/segtree.hpp"
#include "graph/graph.hpp"
#include "monoid/add.hpp"
#include "graph/tree/heavy_light_decomposition.hpp"
#include <iostream>
#include <vector>

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

    m1une::tree::HeavyLightDecomposition<int> hld(g, 0);
    std::vector<long long> base(3, 1);
    m1une::ds::Segtree<m1une::monoid::Add<long long>> seg(base);

    long long sum = 0;
    hld.for_each_path(0, 2, [&](int l, int r, bool) {
        sum += seg.prod(l, r);
    });
    std::cout << sum << "\n"; // 3
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP
#define M1UNE_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP 1

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

#include "../graph.hpp"

namespace m1une {
namespace tree {

struct HldPathSegment {
    int l;
    int r;
    bool reversed;
};

template <class T = int>
struct HeavyLightDecomposition {
    using cost_type = T;
    using edge_type = m1une::graph::Edge<T>;

    int root;
    std::vector<int> parent;
    std::vector<int> parent_edge;
    std::vector<int> depth;
    std::vector<T> dist;
    std::vector<int> subtree_size;
    std::vector<int> heavy;
    std::vector<int> head;
    std::vector<int> tin;
    std::vector<int> tout;
    std::vector<int> order;

   private:
    int _n;

    void check_vertex(int v) const {
        assert(0 <= v && v < _n);
        assert(tin[v] != -1);
    }

    static void add_segment(std::vector<HldPathSegment>& result, int l, int r, bool reversed) {
        if (l < r) result.push_back({l, r, reversed});
    }

   public:
    HeavyLightDecomposition() : root(-1), _n(0) {}
    explicit HeavyLightDecomposition(const m1une::graph::Graph<T>& g, int root_ = 0) {
        build(g, root_);
    }

    void build(const m1une::graph::Graph<T>& g, int root_ = 0) {
        _n = g.size();
        root = _n == 0 ? -1 : root_;
        parent.assign(_n, -2);
        parent_edge.assign(_n, -1);
        depth.assign(_n, 0);
        dist.assign(_n, T(0));
        subtree_size.assign(_n, 1);
        heavy.assign(_n, -1);
        head.assign(_n, -1);
        tin.assign(_n, -1);
        tout.assign(_n, -1);
        order.clear();
        order.reserve(_n);
        if (_n == 0) return;
        assert(0 <= root && root < _n);

        std::vector<int> dfs_order;
        dfs_order.reserve(_n);
        std::vector<int> stack = {root};
        parent[root] = -1;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            dfs_order.push_back(v);
            for (const auto& e : g[v]) {
                if (!e.alive) continue;
                if (parent[e.to] != -2) continue;
                parent[e.to] = v;
                parent_edge[e.to] = e.id;
                depth[e.to] = depth[v] + 1;
                dist[e.to] = dist[v] + e.cost;
                stack.push_back(e.to);
            }
        }

        for (int i = int(dfs_order.size()) - 1; i >= 0; i--) {
            int v = dfs_order[i];
            if (parent[v] == -1) continue;
            int p = parent[v];
            subtree_size[p] += subtree_size[v];
            if (heavy[p] == -1 || subtree_size[heavy[p]] < subtree_size[v]) heavy[p] = v;
        }

        order.assign(dfs_order.size(), -1);
        int timer = 0;
        std::vector<std::pair<int, int>> starts = {std::pair<int, int>{root, root}};
        while (!starts.empty()) {
            auto [start, h] = starts.back();
            starts.pop_back();
            for (int v = start; v != -1; v = heavy[v]) {
                head[v] = h;
                tin[v] = timer;
                order[timer++] = v;
                for (auto it = g[v].rbegin(); it != g[v].rend(); ++it) {
                    if (!it->alive) continue;
                    int to = it->to;
                    if (parent[to] != v || to == heavy[v]) continue;
                    starts.push_back({to, to});
                }
            }
        }
        for (int i = int(dfs_order.size()) - 1; i >= 0; i--) {
            int v = dfs_order[i];
            tout[v] = tin[v] + subtree_size[v];
        }
    }

    int size() const {
        return _n;
    }

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

    bool is_ancestor(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    }

    int lca(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
            u = parent[head[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }

    int dist_edges(int u, int v) const {
        int w = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[w];
    }

    T dist_cost(int u, int v) const {
        int w = lca(u, v);
        return dist[u] + dist[v] - dist[w] - dist[w];
    }

    int kth_ancestor(int v, int k) const {
        check_vertex(v);
        assert(0 <= k);
        while (v != -1) {
            int h = head[v];
            int len = depth[v] - depth[h];
            if (k <= len) return order[tin[v] - k];
            k -= len + 1;
            v = parent[h];
        }
        return -1;
    }

    int jump(int from, int to, int k) const {
        check_vertex(from);
        check_vertex(to);
        assert(0 <= k);
        int w = lca(from, to);
        int up_len = depth[from] - depth[w];
        int down_len = depth[to] - depth[w];
        if (up_len + down_len < k) return -1;
        if (k <= up_len) return kth_ancestor(from, k);
        return kth_ancestor(to, down_len - (k - up_len));
    }

    std::pair<int, int> subtree_range(int v, bool edge = false) const {
        check_vertex(v);
        return {tin[v] + (edge ? 1 : 0), tout[v]};
    }

    std::vector<HldPathSegment> path_segments(int u, int v, bool edge = false) const {
        check_vertex(u);
        check_vertex(v);
        std::vector<HldPathSegment> result, down;
        while (head[u] != head[v]) {
            if (depth[head[u]] >= depth[head[v]]) {
                add_segment(result, tin[head[u]], tin[u] + 1, true);
                u = parent[head[u]];
            } else {
                add_segment(down, tin[head[v]], tin[v] + 1, false);
                v = parent[head[v]];
            }
        }

        if (depth[u] >= depth[v]) {
            add_segment(result, tin[v] + (edge ? 1 : 0), tin[u] + 1, true);
        } else {
            add_segment(down, tin[u] + (edge ? 1 : 0), tin[v] + 1, false);
        }
        std::reverse(down.begin(), down.end());
        result.insert(result.end(), down.begin(), down.end());
        return result;
    }

    template <class F>
    void for_each_path(int u, int v, F f, bool edge = false) const {
        for (auto seg : path_segments(u, v, edge)) f(seg.l, seg.r, seg.reversed);
    }
};

}  // namespace tree
}  // namespace m1une

#endif  // M1UNE_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP

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



#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#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 10 "graph/tree/heavy_light_decomposition.hpp"

namespace m1une {
namespace tree {

struct HldPathSegment {
    int l;
    int r;
    bool reversed;
};

template <class T = int>
struct HeavyLightDecomposition {
    using cost_type = T;
    using edge_type = m1une::graph::Edge<T>;

    int root;
    std::vector<int> parent;
    std::vector<int> parent_edge;
    std::vector<int> depth;
    std::vector<T> dist;
    std::vector<int> subtree_size;
    std::vector<int> heavy;
    std::vector<int> head;
    std::vector<int> tin;
    std::vector<int> tout;
    std::vector<int> order;

   private:
    int _n;

    void check_vertex(int v) const {
        assert(0 <= v && v < _n);
        assert(tin[v] != -1);
    }

    static void add_segment(std::vector<HldPathSegment>& result, int l, int r, bool reversed) {
        if (l < r) result.push_back({l, r, reversed});
    }

   public:
    HeavyLightDecomposition() : root(-1), _n(0) {}
    explicit HeavyLightDecomposition(const m1une::graph::Graph<T>& g, int root_ = 0) {
        build(g, root_);
    }

    void build(const m1une::graph::Graph<T>& g, int root_ = 0) {
        _n = g.size();
        root = _n == 0 ? -1 : root_;
        parent.assign(_n, -2);
        parent_edge.assign(_n, -1);
        depth.assign(_n, 0);
        dist.assign(_n, T(0));
        subtree_size.assign(_n, 1);
        heavy.assign(_n, -1);
        head.assign(_n, -1);
        tin.assign(_n, -1);
        tout.assign(_n, -1);
        order.clear();
        order.reserve(_n);
        if (_n == 0) return;
        assert(0 <= root && root < _n);

        std::vector<int> dfs_order;
        dfs_order.reserve(_n);
        std::vector<int> stack = {root};
        parent[root] = -1;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            dfs_order.push_back(v);
            for (const auto& e : g[v]) {
                if (!e.alive) continue;
                if (parent[e.to] != -2) continue;
                parent[e.to] = v;
                parent_edge[e.to] = e.id;
                depth[e.to] = depth[v] + 1;
                dist[e.to] = dist[v] + e.cost;
                stack.push_back(e.to);
            }
        }

        for (int i = int(dfs_order.size()) - 1; i >= 0; i--) {
            int v = dfs_order[i];
            if (parent[v] == -1) continue;
            int p = parent[v];
            subtree_size[p] += subtree_size[v];
            if (heavy[p] == -1 || subtree_size[heavy[p]] < subtree_size[v]) heavy[p] = v;
        }

        order.assign(dfs_order.size(), -1);
        int timer = 0;
        std::vector<std::pair<int, int>> starts = {std::pair<int, int>{root, root}};
        while (!starts.empty()) {
            auto [start, h] = starts.back();
            starts.pop_back();
            for (int v = start; v != -1; v = heavy[v]) {
                head[v] = h;
                tin[v] = timer;
                order[timer++] = v;
                for (auto it = g[v].rbegin(); it != g[v].rend(); ++it) {
                    if (!it->alive) continue;
                    int to = it->to;
                    if (parent[to] != v || to == heavy[v]) continue;
                    starts.push_back({to, to});
                }
            }
        }
        for (int i = int(dfs_order.size()) - 1; i >= 0; i--) {
            int v = dfs_order[i];
            tout[v] = tin[v] + subtree_size[v];
        }
    }

    int size() const {
        return _n;
    }

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

    bool is_ancestor(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    }

    int lca(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
            u = parent[head[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }

    int dist_edges(int u, int v) const {
        int w = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[w];
    }

    T dist_cost(int u, int v) const {
        int w = lca(u, v);
        return dist[u] + dist[v] - dist[w] - dist[w];
    }

    int kth_ancestor(int v, int k) const {
        check_vertex(v);
        assert(0 <= k);
        while (v != -1) {
            int h = head[v];
            int len = depth[v] - depth[h];
            if (k <= len) return order[tin[v] - k];
            k -= len + 1;
            v = parent[h];
        }
        return -1;
    }

    int jump(int from, int to, int k) const {
        check_vertex(from);
        check_vertex(to);
        assert(0 <= k);
        int w = lca(from, to);
        int up_len = depth[from] - depth[w];
        int down_len = depth[to] - depth[w];
        if (up_len + down_len < k) return -1;
        if (k <= up_len) return kth_ancestor(from, k);
        return kth_ancestor(to, down_len - (k - up_len));
    }

    std::pair<int, int> subtree_range(int v, bool edge = false) const {
        check_vertex(v);
        return {tin[v] + (edge ? 1 : 0), tout[v]};
    }

    std::vector<HldPathSegment> path_segments(int u, int v, bool edge = false) const {
        check_vertex(u);
        check_vertex(v);
        std::vector<HldPathSegment> result, down;
        while (head[u] != head[v]) {
            if (depth[head[u]] >= depth[head[v]]) {
                add_segment(result, tin[head[u]], tin[u] + 1, true);
                u = parent[head[u]];
            } else {
                add_segment(down, tin[head[v]], tin[v] + 1, false);
                v = parent[head[v]];
            }
        }

        if (depth[u] >= depth[v]) {
            add_segment(result, tin[v] + (edge ? 1 : 0), tin[u] + 1, true);
        } else {
            add_segment(down, tin[u] + (edge ? 1 : 0), tin[v] + 1, false);
        }
        std::reverse(down.begin(), down.end());
        result.insert(result.end(), down.begin(), down.end());
        return result;
    }

    template <class F>
    void for_each_path(int u, int v, F f, bool edge = false) const {
        for (auto seg : path_segments(u, v, edge)) f(seg.l, seg.r, seg.reversed);
    }
};

}  // namespace tree
}  // namespace m1une

m1une's library

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

Heavy Light Decomposition
(graph/tree/heavy_light_decomposition.hpp)

Overview

Path Segments

Public Members

Methods

Example

Depends on

Required by

Verified with

Code

Heavy Light Decomposition (graph/tree/heavy_light_decomposition.hpp)

Overview

Path Segments

Public Members

Methods

Example

Depends on

Required by

Verified with

Code

Heavy Light Decomposition
(graph/tree/heavy_light_decomposition.hpp)