セグメント木は、配列上の区間和や最大値などの情報を効率的に管理するためのデータ構造であり、クエリや更新を \(O(\log n)\) で処理できる。しかし、問題が「配列」ではなく「木構造」に拡張され、任意の2ノード間のパス上の情報を維持・操作したい場合、単純にセグメント木を適用することはできない。

木上のパスを線形構造に変換するアイデア

木は分岐構造を持つため、ノード間に自然な連続性がない。ノード \(u\) から \(v\) へのパスは、LCA（最近共通祖先）を経由する2本のパスに分割されるが、これをナイーブに走査すると \(O(n)\) かかる。大規模な木では非現実的である。

そこで登場するのが重軽分解（Heavy-Light Decomposition, HLD）である。この手法は、木を「連続したチェーン」に分割し、各チェーンを線形構造として扱えるようにすることで、パス操作をセグメント木などの効率的なデータ構造と組み合わせることを可能にする。

重軽分解の基本原理：長子継承戦略

各ノードについて、その子の中で部分木のサイズが最大のものを「重子（heavy child）」と定義する。親と重子を結ぶ辺を「重辺（heavy edge）」、それ以外を「軽辺（light edge）」と呼ぶ。重辺のみでつながったパスを「重チェーン（heavy path）」とし、これにより木全体を複数のチェーンに分割する。

重要な観察として、任意のノードから根へのパス上に存在する軽辺の数は \(O(\log n)\) 以下である。なぜなら、軽辺を1つ進むたびに部分木のサイズが半分以下になるため、高々 \(\log_2 n\) 回しか起こらないからである。

実装手順：2回のDFSによる前処理

重軽分解の実装は以下の2段階で行う。

第1回DFS：部分木サイズと重子の決定

各ノードについて、深さ、親、部分木サイズ、重子を計算する。

第2回DFS：DFS順序（dfn）とチェーン先頭（top）の割り当て

重子を優先して再帰的に訪問することで、同一重チェーン内のノードが連続したDFS順序（dfn）を持つようにする。同時に、各ノードが属するチェーンの先頭（top）を記録する。

struct HLD {
    int n;
    vector<vector<int>> g;
    vector<int> parent, depth, subtree_size, heavy, dfn, top;
    int timer = 0;

    HLD(int n) : n(n), g(n), parent(n), depth(n), subtree_size(n, 1),
                 heavy(n, -1), dfn(n), top(n) {}

    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    void dfs1(int u, int p) {
        parent[u] = p;
        depth[u] = (p == -1 ? 0 : depth[p] + 1);
        int max_size = 0;
        for (int v : g[u]) {
            if (v == p) continue;
            dfs1(v, u);
            subtree_size[u] += subtree_size[v];
            if (subtree_size[v] > max_size) {
                max_size = subtree_size[v];
                heavy[u] = v;
            }
        }
    }

    void dfs2(int u, int p, int chain_top) {
        dfn[u] = timer++;
        top[u] = chain_top;
        if (heavy[u] != -1) {
            dfs2(heavy[u], u, chain_top);
        }
        for (int v : g[u]) {
            if (v == p || v == heavy[u]) continue;
            dfs2(v, u, v);
        }
    }

    void build(int root = 0) {
        dfs1(root, -1);
        dfs2(root, -1, root);
    }
};

重軽分解の核心的性質

• 連続性：同一重チェーン内のノードは、dfn 順で連続する。よって、チェーン上の操作はセグメント木の区間操作に帰着できる。
• 対数個のチェーン分割：任意の2ノード間のパスは、高々 \(O(\log n)\) 個の重チェーンに分割される。

パス操作の実行方法

ノード \(u\) と \(v\) のパスを処理する際、チェーン先頭の深さが深い方を選び、そのチェーン全体（dfn[top[u]] から dfn[u]）に対してセグメント木操作を行い、その後 u = parent[top[u]] として上にジャンプする。これを両者が同じチェーンに入るまで繰り返す。

void process_path(HLD& hld, SegTree& seg, int u, int v) {
    while (hld.top[u] != hld.top[v]) {
        if (hld.depth[hld.top[u]] < hld.depth[hld.top[v]]) swap(u, v);
        seg.update(hld.dfn[hld.top[u]], hld.dfn[u], value); // 例：区間更新
        u = hld.parent[hld.top[u]];
    }
    if (hld.dfn[u] > hld.dfn[v]) swap(u, v);
    seg.update(hld.dfn[u], hld.dfn[v], value);
}

LCAの高速計算

重軽分解を用いると、LCAも同様のジャンプ戦略で求められる：

int lca(HLD& hld, int u, int v) {
    while (hld.top[u] != hld.top[v]) {
        if (hld.depth[hld.top[u]] < hld.depth[hld.top[v]]) swap(u, v);
        u = hld.parent[hld.top[u]];
    }
    return (hld.dfn[u] < hld.dfn[v]) ? u : v;
}

この方法のクエリ計算量は \(O(\log n)\) であり、すでに重軽分解を用いてパス操作を行っているシステムでは、追加コストなくLCAを求められるという利点がある。

計算量まとめ

重軽分解は、実装の簡潔さと汎用性のバランスが良く、特にパス上の動的クエリを伴う問題において強力なツールとなる。