HL分解 (Heavy-Light Decomposition)
(graph/heavy_light_decomposition.hpp)

• View this file on GitHub
• Last update: 2026-10-19 02:29:38+09:00
• Include: #include "graph/heavy_light_decomposition.hpp"

概要

• 木をパスに分解し、パスや部分木に対するクエリを区間クエリに帰着させる。
• 各頂点 v には番号 index(v) が振られ、部分木は番号の連続区間、任意のパスは $\mathcal O(\log N)$ 個の連続区間になる。

使い方

• heavy_light_decomposition(n, root = 0): $\mathrm n$ 頂点で初期化する。頂点 root が根になる。
• add_edge(u, v): 頂点 u と頂点 v とを結ぶ辺を追加する。
• build(): 構築する。
• index(v): 頂点 v の番号を返す。
• vertex(i): 番号 i の頂点を返す。
• subtree(v): 頂点 v の部分木に対応する番号の区間 $[l, r)$ を返す。
• edge_index(i): i 番目に add_edge した辺の番号を返す。辺の番号は子側の頂点の番号で、辺に値を持たせるときの格納位置になる。
• depth(v): 頂点 v の深さを返す。
• parent(v): 頂点 v の親を返す。根なら -1。
• head_of(v): 頂点 v を含む heavy path の最も浅い頂点を返す。
• lca(u, v): 頂点 u と頂点 v のLCAを返す。
• lca(u, v, r): 頂点 r を根とみたときの、頂点 u と頂点 v のLCAを返す。
• dist(u, v): 頂点 u と頂点 v との距離を返す。
• la(v, k): 頂点 v の k 個上の祖先を返す。存在しなければ -1。
• jump(s, t, k): 頂点 s から頂点 t へ向かって k 回進んだ頂点を返す。存在しなければ -1。
• in_subtree(u, v): 頂点 v が頂点 u の部分木に含まれるか判定する。
• on_path(s, t, x): 頂点 x が s-t パス上にあるか判定する。
• for_each_vertex(u, v, f): u-v パス上の頂点を番号の区間に分解し、各区間について f(l, r) を呼ぶ。
• for_each_edge(u, v, f): u-v パス上の辺を番号の区間に分解し、各区間について f(l, r) を呼ぶ。辺は子側の頂点の番号で表す。
• for_each_vertex_noncommutative(u, v, f): u から v へ向かう順に区間を f(a, b) で呼ぶ。a < b なら区間 $[a, b)$ を昇順に、a > b なら区間 $[b, a)$ を降順に辿る。
• for_each_edge_noncommutative(u, v, f): 辺版。
• for_each_vertex_in_subtree(v, f): 頂点 v の部分木に含まれる頂点の区間について f(l, r) を呼ぶ。
• for_each_edge_in_subtree(v, f): 頂点 v の部分木に含まれる辺の区間について f(l, r) を呼ぶ。

計算量

• 構築 $\mathcal O(N)$
• lca, dist, la, jump: $\mathcal O(\log N)$
• for_each_*: 区間の個数は $\mathcal O(\log N)$ 個

Verified with

• test/aoj/GRL_5_E.test.cpp
• test/library-checker/jump_on_tree.test.cpp
• test/library-checker/lca_heavy_light_decomposition.test.cpp
• test/library-checker/vertex_add_path_sum.test.cpp
• test/library-checker/vertex_add_subtree_sum.test.cpp
• test/library-checker/vertex_set_path_composite.test.cpp
• test/unit/heavy_light_decomposition.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
struct heavy_light_decomposition {
public:
    heavy_light_decomposition() {
    }
    heavy_light_decomposition(int n, int root = 0)
        : _n(n),
          _root(root),
          g(n),
          sub(n),
          dep(n),
          par(n),
          heavy(n, -1),
          head(n),
          in(n),
          out(n),
          rev(n) {
    }
    void add_edge(int u, int v) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        g[u].push_back(v);
        g[v].push_back(u);
        edges.emplace_back(u, v);
    }
    void build() {
        par[_root] = -1;
        dep[_root] = 0;
        std::vector<int> order, st = {_root};
        order.reserve(_n);
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            order.push_back(v);
            for (int c : g[v]) {
                if (c == par[v]) continue;
                par[c] = v;
                dep[c] = dep[v] + 1;
                st.push_back(c);
            }
        }
        for (int i = _n - 1; i >= 0; i--) {
            int v = order[i], p = par[v];
            sub[v]++;
            if (p == -1) continue;
            sub[p] += sub[v];
            if (heavy[p] == -1 || sub[v] > sub[heavy[p]]) heavy[p] = v;
        }
        int t = 0;
        head[_root] = _root;
        st = {_root};
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            in[v] = t++;
            rev[in[v]] = v;
            out[v] = in[v] + sub[v];
            for (int c : g[v]) {
                if (c == par[v] || c == heavy[v]) continue;
                head[c] = c;
                st.push_back(c);
            }
            if (heavy[v] != -1) {
                head[heavy[v]] = head[v];
                st.push_back(heavy[v]);
            }
        }
    }

    int index(int v) const {
        return in[v];
    }
    int vertex(int i) const {
        return rev[i];
    }
    std::pair<int, int> subtree(int v) const {
        return {in[v], out[v]};
    }
    int edge_index(int i) const {
        assert(0 <= i && i < (int)edges.size());
        auto [u, v] = edges[i];
        return in[par[u] == v ? u : v];
    }
    int depth(int v) const {
        return dep[v];
    }
    int parent(int v) const {
        return par[v];
    }
    int head_of(int v) const {
        return head[v];
    }
    int lca(int u, int v) const {
        while (head[u] != head[v]) {
            if (dep[head[u]] < dep[head[v]]) std::swap(u, v);
            u = par[head[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    int lca(int u, int v, int r) const {
        return lca(u, v) ^ lca(v, r) ^ lca(r, u);
    }
    int dist(int u, int v) const {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    int la(int v, int k) const {
        if (k < 0 || dep[v] < k) return -1;
        while (dep[v] - dep[head[v]] < k) {
            k -= dep[v] - dep[head[v]] + 1;
            v = par[head[v]];
        }
        return rev[in[v] - k];
    }
    int jump(int s, int t, int k) const {
        int l = lca(s, t);
        int d = dep[s] + dep[t] - 2 * dep[l];
        if (k < 0 || d < k) return -1;
        if (k <= dep[s] - dep[l]) return la(s, k);
        return la(t, d - k);
    }
    bool in_subtree(int u, int v) const {
        return in[u] <= in[v] && in[v] < out[u];
    }
    bool on_path(int s, int t, int x) const {
        return dist(s, x) + dist(x, t) == dist(s, t);
    }

    template <typename F>
    void for_each_vertex(int u, int v, const F& f) const {
        for_each(u, v, false, f);
    }
    template <typename F>
    void for_each_edge(int u, int v, const F& f) const {
        for_each(u, v, true, f);
    }
    template <typename F>
    void for_each_vertex_noncommutative(int u, int v, const F& f) const {
        for_each_noncommutative(u, v, false, f);
    }
    template <typename F>
    void for_each_edge_noncommutative(int u, int v, const F& f) const {
        for_each_noncommutative(u, v, true, f);
    }
    template <typename F>
    void for_each_vertex_in_subtree(int v, const F& f) const {
        f(in[v], out[v]);
    }
    template <typename F>
    void for_each_edge_in_subtree(int v, const F& f) const {
        if (in[v] + 1 < out[v]) f(in[v] + 1, out[v]);
    }

private:
    int _n, _root;
    std::vector<std::vector<int>> g;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> sub, dep, par, heavy, head, in, out, rev;
    template <typename F>
    void for_each(int u, int v, bool edge, const F& f) const {
        while (head[u] != head[v]) {
            if (dep[head[u]] < dep[head[v]]) std::swap(u, v);
            f(in[head[u]], in[u] + 1);
            u = par[head[u]];
        }
        if (dep[u] > dep[v]) std::swap(u, v);
        if (in[u] + edge < in[v] + 1) f(in[u] + edge, in[v] + 1);
    }
    template <typename F>
    void for_each_noncommutative(int u, int v, bool edge, const F& f) const {
        std::vector<std::pair<int, int>> down;
        while (head[u] != head[v]) {
            if (dep[head[u]] >= dep[head[v]]) {
                f(in[u] + 1, in[head[u]]);
                u = par[head[u]];
            } else {
                down.emplace_back(in[head[v]], in[v] + 1);
                v = par[head[v]];
            }
        }
        if (dep[u] > dep[v]) {
            if (in[v] + edge < in[u] + 1) f(in[u] + 1, in[v] + edge);
        } else {
            if (in[u] + edge < in[v] + 1) f(in[u] + edge, in[v] + 1);
        }
        for (auto it = down.rbegin(); it != down.rend(); it++) {
            f(it->first, it->second);
        }
    }
};

#line 2 "graph/heavy_light_decomposition.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
struct heavy_light_decomposition {
public:
    heavy_light_decomposition() {
    }
    heavy_light_decomposition(int n, int root = 0)
        : _n(n),
          _root(root),
          g(n),
          sub(n),
          dep(n),
          par(n),
          heavy(n, -1),
          head(n),
          in(n),
          out(n),
          rev(n) {
    }
    void add_edge(int u, int v) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        g[u].push_back(v);
        g[v].push_back(u);
        edges.emplace_back(u, v);
    }
    void build() {
        par[_root] = -1;
        dep[_root] = 0;
        std::vector<int> order, st = {_root};
        order.reserve(_n);
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            order.push_back(v);
            for (int c : g[v]) {
                if (c == par[v]) continue;
                par[c] = v;
                dep[c] = dep[v] + 1;
                st.push_back(c);
            }
        }
        for (int i = _n - 1; i >= 0; i--) {
            int v = order[i], p = par[v];
            sub[v]++;
            if (p == -1) continue;
            sub[p] += sub[v];
            if (heavy[p] == -1 || sub[v] > sub[heavy[p]]) heavy[p] = v;
        }
        int t = 0;
        head[_root] = _root;
        st = {_root};
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            in[v] = t++;
            rev[in[v]] = v;
            out[v] = in[v] + sub[v];
            for (int c : g[v]) {
                if (c == par[v] || c == heavy[v]) continue;
                head[c] = c;
                st.push_back(c);
            }
            if (heavy[v] != -1) {
                head[heavy[v]] = head[v];
                st.push_back(heavy[v]);
            }
        }
    }

    int index(int v) const {
        return in[v];
    }
    int vertex(int i) const {
        return rev[i];
    }
    std::pair<int, int> subtree(int v) const {
        return {in[v], out[v]};
    }
    int edge_index(int i) const {
        assert(0 <= i && i < (int)edges.size());
        auto [u, v] = edges[i];
        return in[par[u] == v ? u : v];
    }
    int depth(int v) const {
        return dep[v];
    }
    int parent(int v) const {
        return par[v];
    }
    int head_of(int v) const {
        return head[v];
    }
    int lca(int u, int v) const {
        while (head[u] != head[v]) {
            if (dep[head[u]] < dep[head[v]]) std::swap(u, v);
            u = par[head[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    int lca(int u, int v, int r) const {
        return lca(u, v) ^ lca(v, r) ^ lca(r, u);
    }
    int dist(int u, int v) const {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    int la(int v, int k) const {
        if (k < 0 || dep[v] < k) return -1;
        while (dep[v] - dep[head[v]] < k) {
            k -= dep[v] - dep[head[v]] + 1;
            v = par[head[v]];
        }
        return rev[in[v] - k];
    }
    int jump(int s, int t, int k) const {
        int l = lca(s, t);
        int d = dep[s] + dep[t] - 2 * dep[l];
        if (k < 0 || d < k) return -1;
        if (k <= dep[s] - dep[l]) return la(s, k);
        return la(t, d - k);
    }
    bool in_subtree(int u, int v) const {
        return in[u] <= in[v] && in[v] < out[u];
    }
    bool on_path(int s, int t, int x) const {
        return dist(s, x) + dist(x, t) == dist(s, t);
    }

    template <typename F>
    void for_each_vertex(int u, int v, const F& f) const {
        for_each(u, v, false, f);
    }
    template <typename F>
    void for_each_edge(int u, int v, const F& f) const {
        for_each(u, v, true, f);
    }
    template <typename F>
    void for_each_vertex_noncommutative(int u, int v, const F& f) const {
        for_each_noncommutative(u, v, false, f);
    }
    template <typename F>
    void for_each_edge_noncommutative(int u, int v, const F& f) const {
        for_each_noncommutative(u, v, true, f);
    }
    template <typename F>
    void for_each_vertex_in_subtree(int v, const F& f) const {
        f(in[v], out[v]);
    }
    template <typename F>
    void for_each_edge_in_subtree(int v, const F& f) const {
        if (in[v] + 1 < out[v]) f(in[v] + 1, out[v]);
    }

private:
    int _n, _root;
    std::vector<std::vector<int>> g;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> sub, dep, par, heavy, head, in, out, rev;
    template <typename F>
    void for_each(int u, int v, bool edge, const F& f) const {
        while (head[u] != head[v]) {
            if (dep[head[u]] < dep[head[v]]) std::swap(u, v);
            f(in[head[u]], in[u] + 1);
            u = par[head[u]];
        }
        if (dep[u] > dep[v]) std::swap(u, v);
        if (in[u] + edge < in[v] + 1) f(in[u] + edge, in[v] + 1);
    }
    template <typename F>
    void for_each_noncommutative(int u, int v, bool edge, const F& f) const {
        std::vector<std::pair<int, int>> down;
        while (head[u] != head[v]) {
            if (dep[head[u]] >= dep[head[v]]) {
                f(in[u] + 1, in[head[u]]);
                u = par[head[u]];
            } else {
                down.emplace_back(in[head[v]], in[v] + 1);
                v = par[head[v]];
            }
        }
        if (dep[u] > dep[v]) {
            if (in[v] + edge < in[u] + 1) f(in[u] + 1, in[v] + edge);
        } else {
            if (in[u] + edge < in[v] + 1) f(in[u] + edge, in[v] + 1);
        }
        for (auto it = down.rbegin(); it != down.rend(); it++) {
            f(it->first, it->second);
        }
    }
};

Back to top page