重軽分解
(library/graph/tree/heavy_light_decomposition.hpp)

View this file on GitHub
Last update: 2026-01-21 19:52:16+09:00
Include: #include "library/graph/tree/heavy_light_decomposition.hpp"

重軽分解

できること

木構造を配列として扱えるため、セグ木などと相性がよい
- 木上のダブリング→HL分解してセグ木、などとできる
- 動的パス更新/取得: 頂点u,v間の辺の重みを足す、パス上の最大値など
パス上のクエリ: 頂点uからvへの最短パス上にある値の、合計や最大
パス上の一括更新: 頂点uからvへの最短パス上の値を一括更新
LCA取得: ダブリング実装より定数倍が速い
LA取得: Level Ancestor 頂点vのk個上の親を取得
部分木クエリ: 頂点vの部分木全体に対する操作
指定された頂点たちのLCA関係を保って木を圧縮してできる補助的な木「Auxiliary Tree （虚樹）」を作る
参考: https://smijake3.hatenablog.com/entry/2019/09/15/200200
ちょっとした解説
- 子孫数（部分木サイズ）が多い子への辺をHeavyEdge、それ以外をLight Edgeと呼ぶ
- HeavyEdgeをつなげていくと、木全体がいくつかの「太いパス」に分解される

また、構造体中で管理する配列の役割は以下

メンバ	役割
sz	そのノードを根とする部分木のサイズ
in	HLDの新ノード順、DFS行きがけ順。セグ木のindexに使う
out	部分木終端のin番号 in[v]からout[v]までがvを根とする部分木全体
head	そのノードが属するパスの先頭ノード
rev	in番号から元のノード番号を逆引きする配列 rev[in[v]] == vである
par	ノードの親ノード
dep	ノードの深さ

計算量

頂点数をN

構築 build: $O(N)$ in順で一列の配列になる
LCA lca(u, v): $O(\log N)$
LA la(v, k): $O(\log N)$
2点間距離 dist(u, v): $O(\log N)$
パスクエリ query add: $O(\log^2 N)$ (セグ木分で2乗)
部分木クエリ: $O(log N)$ (セグ木分)
虚樹構築 compress: $O(K \log K)$ Kは指定頂点集合の要素数

使い方

verifyしてるプログラムファイルのが分かりやすいかも。

int N;
cin >> N;
vector<int> S(N);
cin >> S;

HeavyLightDecomposition hld(N);
hld.read(N - 1);  // グラフ構造体を継承している
hld.build(0); // 根を指定してビルド

int lca_node = hld.lca(2, 4);    // 2と4の共通祖先
int d = hld.dist(2, 4);         // 2と4の距離
int anc = hld.la(4, 2);         // 4から2代上の親 (k=0なら自分自身)


// 遅延セグ木を用意
vector<int> A(N);
for (int i = 0; i < N; ++i) {
  A[i] = S[hld.rev[i]]; // inやrevをうまく使う
  // 場合によって、新規Node構造体を作って、モノイドを定義
}
LazySegmentTree<int, int> seg(
    Monoid::Add::op,            // 区間取得の演算 (足し算)
    Monoid::Add::e,             // 単位元 (0)
    Monoid::Add::op,            // 更新操作のマージ (足し算)
    Monoid::Add::e,             // 更新の単位元 (0)
    MonoidAct::AddAdd::op,      // ノードへの作用 (加算 * 区間サイズ)
    A
);

int u = 0, v = 4;

// 0番から4番のパス上のノードすべてに +10
hld.add(u, v, [&](int l, int r) {
    seg.apply(l, r, 10);
});

// 0番から4番のパス上の合計を取得
long long res = hld.query(u, v, 0LL, // 初期値
    [&](int l, int r) { return seg.prod(l, r); }, // セグ木を利用
    [](long long a, long long b) { return a + b; } // 計上の二項演算
);

Depends on

Verified with

木 - HLDのテスト木上クエリ:最大連続部分列和 (tests/graph.tree.heavy_light_decomposition.test.cpp)

Code

#pragma once
#include "library/graph/base/graph.hpp"
struct HeavyLightDecomposition : Graph {
  public:
    using Graph::G;
    using Graph::Graph;
    vector<int> sz, in, out, head, rev, par, dep;
    void build(int root = 0) {
        sz.assign(G.size(), 0);
        in.assign(G.size(), 0);
        out.assign(G.size(), 0);
        head.assign(G.size(), 0);
        rev.assign(G.size(), 0);
        par.assign(G.size(), 0);
        dep.assign(G.size(), 0);
        dfs_sz(root, -1, 0);
        int t = 0;
        head[root] = root;
        dfs_hld(root, -1, t);
    }
    /* k: 0-indexed */
    int la(int v, int k) {
        while (1) {
            int u = head[v];
            if (in[v] - k >= in[u]) return rev[in[v] - k];
            k -= in[v] - in[u] + 1;
            v = par[u];
        }
    }
    int lca(int u, int v) const {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) return u;
        }
    }
    int dist(int u, int v) const {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    template <typename E, typename Q, typename F, typename S>
    E query(int u, int v, const E &ti, const Q &q, const F &f, const S &s,
            bool edge = false) {
        E l = ti, r = ti;
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v), swap(l, r);
            if (head[u] == head[v]) break;
            l = f(q(in[head[v]], in[v] + 1), l);
        }
        return s(f(q(in[u] + edge, in[v] + 1), l), r);
    }
    template <typename E, typename Q, typename F>
    E query(int u, int v, const E &ti, const Q &q, const F &f,
            bool edge = false) {
        return query(u, v, ti, q, f, f, edge);
    }
    template <typename Q>
    void add(int u, int v, const Q &q, bool edge = false) {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) break;
            q(in[head[v]], in[v] + 1);
        }
        q(in[u] + edge, in[v] + 1);
    }
    /* {parent, child} */
    vector<pair<int, int>> compress(vector<int> &remark) {
        auto cmp = [&](int a, int b) { return in[a] < in[b]; };
        sort(begin(remark), end(remark), cmp);
        remark.erase(unique(begin(remark), end(remark)), end(remark));
        int K = (int)remark.size();
        for (int k = 1; k < K; k++)
            remark.emplace_back(lca(remark[k - 1], remark[k]));
        sort(begin(remark), end(remark), cmp);
        remark.erase(unique(begin(remark), end(remark)), end(remark));
        vector<pair<int, int>> es;
        stack<int> st;
        for (auto &k : remark) {
            while (!st.empty() && out[st.top()] <= in[k]) st.pop();
            if (!st.empty()) es.emplace_back(st.top(), k);
            st.emplace(k);
        }
        return es;
    }
    explicit HeavyLightDecomposition(const Graph &G) : Graph(G) {}

  private:
    void dfs_sz(int idx, int p, int d) {
        dep[idx] = d;
        par[idx] = p;
        sz[idx] = 1;
        if (G[idx].size() && G[idx][0].to == p) swap(G[idx][0], G[idx].back());
        for (auto &&edge : G[idx]) {
            if (edge.to == p) continue;
            dfs_sz(edge.to, idx, d + 1);
            sz[idx] += sz[edge.to];
            if (sz[G[idx][0].to] < sz[edge.to]) swap(G[idx][0].to, edge.to);
        }
    }
    void dfs_hld(int idx, int p, int &times) {
        in[idx] = times++;
        rev[in[idx]] = idx;
        for (auto &&edge : G[idx]) {
            if (edge.to == p) continue;
            head[edge.to] = (G[idx][0].to == edge.to ? head[idx] : edge.to);
            dfs_hld(edge.to, idx, times);
        }
        out[idx] = times;
    }
};

#line 2 "library/graph/base/edge.hpp"
struct Edge {
    int from, to;
    long long cost;
    int idx;
    Edge(int from, int to, long long cost = 1, int idx = -1)
        : from(from), to(to), cost(cost), idx(idx) {}
};
#line 3 "library/graph/base/graph.hpp"
struct Graph {
    int N;
    vector<vector<Edge>> G;
    int es;
    Graph() = default;
    Graph(int N) : N(N), G(N), es(0) {}
    const vector<Edge> &operator[](int v) const { return G[v]; }
    int size() const { return N; }
    void add(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es++));
    }
    void add_both(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es));
        G[to].push_back(Edge(to, from, cost, es++));
    }
    void read(int M, int padding = -1, bool weighted = false,
              bool directed = false) {
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            u += padding, v += padding;
            long long cost = 1ll;
            if (weighted) cin >> cost;
            if (directed) {
                add(u, v, cost);
            } else {
                add_both(u, v, cost);
            }
        }
    }
};
#line 3 "library/graph/tree/heavy_light_decomposition.hpp"
struct HeavyLightDecomposition : Graph {
  public:
    using Graph::G;
    using Graph::Graph;
    vector<int> sz, in, out, head, rev, par, dep;
    void build(int root = 0) {
        sz.assign(G.size(), 0);
        in.assign(G.size(), 0);
        out.assign(G.size(), 0);
        head.assign(G.size(), 0);
        rev.assign(G.size(), 0);
        par.assign(G.size(), 0);
        dep.assign(G.size(), 0);
        dfs_sz(root, -1, 0);
        int t = 0;
        head[root] = root;
        dfs_hld(root, -1, t);
    }
    /* k: 0-indexed */
    int la(int v, int k) {
        while (1) {
            int u = head[v];
            if (in[v] - k >= in[u]) return rev[in[v] - k];
            k -= in[v] - in[u] + 1;
            v = par[u];
        }
    }
    int lca(int u, int v) const {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) return u;
        }
    }
    int dist(int u, int v) const {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    template <typename E, typename Q, typename F, typename S>
    E query(int u, int v, const E &ti, const Q &q, const F &f, const S &s,
            bool edge = false) {
        E l = ti, r = ti;
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v), swap(l, r);
            if (head[u] == head[v]) break;
            l = f(q(in[head[v]], in[v] + 1), l);
        }
        return s(f(q(in[u] + edge, in[v] + 1), l), r);
    }
    template <typename E, typename Q, typename F>
    E query(int u, int v, const E &ti, const Q &q, const F &f,
            bool edge = false) {
        return query(u, v, ti, q, f, f, edge);
    }
    template <typename Q>
    void add(int u, int v, const Q &q, bool edge = false) {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) break;
            q(in[head[v]], in[v] + 1);
        }
        q(in[u] + edge, in[v] + 1);
    }
    /* {parent, child} */
    vector<pair<int, int>> compress(vector<int> &remark) {
        auto cmp = [&](int a, int b) { return in[a] < in[b]; };
        sort(begin(remark), end(remark), cmp);
        remark.erase(unique(begin(remark), end(remark)), end(remark));
        int K = (int)remark.size();
        for (int k = 1; k < K; k++)
            remark.emplace_back(lca(remark[k - 1], remark[k]));
        sort(begin(remark), end(remark), cmp);
        remark.erase(unique(begin(remark), end(remark)), end(remark));
        vector<pair<int, int>> es;
        stack<int> st;
        for (auto &k : remark) {
            while (!st.empty() && out[st.top()] <= in[k]) st.pop();
            if (!st.empty()) es.emplace_back(st.top(), k);
            st.emplace(k);
        }
        return es;
    }
    explicit HeavyLightDecomposition(const Graph &G) : Graph(G) {}

  private:
    void dfs_sz(int idx, int p, int d) {
        dep[idx] = d;
        par[idx] = p;
        sz[idx] = 1;
        if (G[idx].size() && G[idx][0].to == p) swap(G[idx][0], G[idx].back());
        for (auto &&edge : G[idx]) {
            if (edge.to == p) continue;
            dfs_sz(edge.to, idx, d + 1);
            sz[idx] += sz[edge.to];
            if (sz[G[idx][0].to] < sz[edge.to]) swap(G[idx][0].to, edge.to);
        }
    }
    void dfs_hld(int idx, int p, int &times) {
        in[idx] = times++;
        rev[in[idx]] = idx;
        for (auto &&edge : G[idx]) {
            if (edge.to == p) continue;
            head[edge.to] = (G[idx][0].to == edge.to ? head[idx] : edge.to);
            dfs_hld(edge.to, idx, times);
        }
        out[idx] = times;
    }
};

重軽分解 (library/graph/tree/heavy_light_decomposition.hpp)

重軽分解

できること

計算量

使い方

Depends on

Verified with

Code

重軽分解
(library/graph/tree/heavy_light_decomposition.hpp)