Heavy Light Decomposition - 重軽分解
(Library/Tree/HeavyLightDecomposition.hpp)

• View this file on GitHub
• Last update: 2026-02-13 15:23:31+09:00
• Include: #include "Library/Tree/HeavyLightDecomposition.hpp"

Attention: このドキュメントは未完成です。

Heavy Light Decomposition - 重軽分解

$n$ 頂点の根付き木 $T$ を $\textrm{O}(\log n)$ 個のパスの集合に分解します。

Function

Constructor

HeavyLightDecomposition(Graph<CostType> &tree, Vertex r = 0)

• 頂点 $r$ を根とする根付き木 $T$ に対して重軽分解を行います。

制約

• $0 \le r \lt n$

計算量

• $\textrm{O}(n)$

---

LowestCommonAncestor

Vertex LowestCommonAncestor(Vertex u, Vertex v) const

• 頂点 $u$ と頂点 $v$ の最小共通祖先の頂点を求めます。

制約

• $0 \le u, v \lt n$

計算量

• $\textrm{O}(\log n)$

---

LevelAncestor

Vertex LevelAncestor(Vertex v, int k)

• 頂点 $v$ から $k$ 回親の頂点を辿った先の頂点を求めます。

制約

• $0 \le v \lt n$
• 頂点 $v$ の深さを $d$ としたとき、$0 \le k \le d$

計算量

• $\textrm{O}(\log n)$

---

Jump

int Jump(Vertex u, Vertex v, int k)

• 頂点 $u$ から頂点 $v$ への $T$ 上の最短パスを通る順に並べた頂点列 $p = (p_0, \dots, p_d)$ において、頂点 $p_k$ を返します。ここで、$d$ は頂点 $u$ から頂点 $v$ への $T$ 上の最短パス長です。
• $k \lt 0$ または $d \lt k$ のとき、-1 を返します。

制約

• $0 \le u, v \lt n$

計算量

• $\textrm{O}(\log n)$

---

PathQuery

vector<PathSegment> PathQuery(Vertex u, Vertex v)

• 頂点 $u$ から頂点 $v$ へのパスを Heavy Path に分解した PathSegment の集合を返します。
• PathSegment $P$ は次の要素からなる構造体です。
  • head_vertex : $P$ のうち最も根に近い頂点番号
  • tail_vertex : $P$ のうち最も葉に近い頂点番号
  • head_index : head_vertex の行きかけ順序 (0-index)
  • tail_index : tail_vertex の行きかけ順序 (0-index)
  • highest : $P$ が最も根に近いパスであること (すなわち、$\textrm{LCA}(u, v)$ を含むこと) を表す真偽値
  • reverse : 頂点 $u$ が tail_vertex であることを表す真偽値
• Segment Tree などと併せて使用することを想定しています。基本的には SortVertex() によって並べ替えたデータを乗せた Segment Tree に対して半開区間 [head_index, tail_index) のクエリを実行すればよいです。
• クエリが辺属性である場合、すなわち頂点 $x$ に対するデータの代わりに、頂点 $x$ とその親の頂点を繋ぐ辺に対するデータを表す場合、$\textrm{LCA}(u, v)$ に対するデータを集計しないようにする必要があります。
  • highest フラグを確認することで解決できます。より具体的には、highest フラグが真であるとき、[head_index + 1, tail_index) を代わりに実行すればよいです。(要 verify)
• Segment Tree などに乗せたデータが可換性を持たないとき、パスの向きに注意する必要があります。
  • 二方向の演算で集計できるように、$2$ 本の Segment Tree を持ちつつ、reverse フラグを確認することで解決できます。より具体的には、reverse フラグの真偽によってクエリを実行するデータ構造を変更すればよいです。実装例は Vertex Set Path Composite を参照してください。

制約

• $0 \le u, v \lt n$

計算量

• $\textrm{O}(\log n)$

---

SubtreeQuery

pair<int, int> SubtreeQuery(Vertex v) const

• 頂点 $v$ を根とする部分木に対応する区間を半開区間で返します。

制約

• $0 \le v \lt n$

計算量

• $\textrm{O}(1)$

---

SortVertex

void SortVertex(vector<T> &A)

• 長さ $n$ の数列 $A = (A_1, \dots, A_n)$ を、頂点の行きかけ順序になるように並べ替えます。

制約

• $

  A

  = n$

計算量

• $\textrm{O}(n)$

---

Depends on

• Library/Common.hpp
• Graph - グラフ構造 (Library/Graph/Graph.hpp)
• Tree - 木 (Library/Tree/Tree.hpp)

Verified with

• verify/LC-JumponTree.test.cpp
• verify/LC-LowestCommonAncestor-HLD.test.cpp
• verify/LC-VertexAddPathSum.test.cpp
• verify/LC-VertexAddSubtreeSum.test.cpp
• verify/LC-VertexSetPathComposite.test.cpp

Code

#include "Tree.hpp"

struct PathSegment{
    PathSegment() = default;
    Vertex head_vertex;
    Vertex tail_vertex;
    int head_index;
    int tail_index;
    bool highest;
    bool reverse;
    friend ostream &operator<<(ostream &os, const PathSegment &p){
        return os << "# Path (" << p.head_vertex << " -> " << p.tail_vertex << ", " << p.head_index << " -> " << p.tail_index << ", " << boolalpha << p.highest << ", " << p.reverse << ")";
    }
};

template<typename WeightType>
class HeavyLightDecomposition{
    public:
    HeavyLightDecomposition(Graph<WeightType> &tree, Vertex r = 0) :
        T(tree), parent(CalculateTreeParent(tree, r)), child(RootedTreeAdjacentList(tree, r)), n((int)tree.VertexSize()), euler_tour_(n), rev_order_(n), depth_(CalculateTreeDepth(tree, r)), belong_hp_id_(n){
        vector<int> ss = CalculateSubtreeSize(T, r);
        for(int i = 0; i < n; ++i){
            if(child[i].empty()) continue;
            nth_element(child[i].begin(), child[i].begin() + 1, child[i].end(), [&](Vertex i, Vertex j){
                return ss[i] > ss[j];
            });
        }
        hp_head_.push_back(r);
        hp_depth_.push_back(0);
        belong_hp_id_[r] = 0;
        timer_ = 0;
        dfs(r, 0, 0);
    }

    Vertex LowestCommonAncestor(Vertex u, Vertex v) const {
        if(PathDepth(u) < PathDepth(v)) swap(u, v);
        while(PathDepth(u) != PathDepth(v)){
            u = parent[Head(u)];
        }
        while(Belong(u) != Belong(v)){
            u = parent[Head(u)];
            v = parent[Head(v)];
        }
        return depth_[u] < depth_[v] ? u : v;
    }

    Vertex LevelAncestor(Vertex v, int k){
        assert(k <= depth_[v]);
        Vertex ret = v;
        while(1){
            int h = Head(ret);
            int x = depth_[ret] - depth_[h];
            if(k <= x){
                ret = RevOrder(PreOrder(ret) - k);
                break;
            }
            ret = parent[h];
            k -= x + 1;
        }
        return ret;
    }

    int Jump(Vertex u, Vertex v, int k){
        Vertex w = LowestCommonAncestor(u, v);
        int p = depth_[u] - depth_[w], q = depth_[v] - depth_[w];
        if(p + q < k || k < 0) return -1;
        if(k <= p) return LevelAncestor(u, k);
        else return LevelAncestor(v, p + q - k);
    }

    vector<PathSegment> PathQuery(Vertex u, Vertex v){
        vector<PathSegment> ret;
        Vertex lca = LowestCommonAncestor(u, v);
        while(Belong(u) != Belong(lca)){
            PathSegment path;
            Vertex h = Head(u);
            path.head_vertex = h, path.tail_vertex = u;
            path.head_index = PreOrder(h), path.tail_index = PreOrder(u) + 1;
            path.highest = false, path.reverse = true;
            ret.push_back(path);
            u = parent[h];
        }
        if(u != lca){
            PathSegment path;
            path.head_vertex = lca, path.tail_vertex = u;
            path.head_index = PreOrder(lca), path.tail_index = PreOrder(u) + 1;
            path.highest = true, path.reverse = true;
            ret.push_back(path);
        }
        int size = ret.size();
        while(Belong(v) != Belong(lca)){
            PathSegment path;
            Vertex h = Head(v);
            path.head_vertex = h, path.tail_vertex = v;
            path.head_index = PreOrder(h), path.tail_index = PreOrder(v) + 1;
            path.highest = false, path.reverse = false;
            ret.push_back(path);
            v = parent[h];
        }
        if(v != lca){
            PathSegment path;
            path.head_vertex = lca, path.tail_vertex = v;
            path.head_index = PreOrder(lca), path.tail_index = PreOrder(v) + 1;
            path.highest = true, path.reverse = false;
            ret.push_back(path);
        }
        if(u == lca && v == lca){
            PathSegment path;
            path.head_vertex = path.tail_vertex = lca;
            path.head_index = PreOrder(lca), path.tail_index = PreOrder(lca) + 1;
            path.highest = true, path.reverse = false;
            ret.push_back(path);
        }
        reverse(ret.begin() + size, ret.end());
        return ret;
    }

    pair<int, int> SubtreeQuery(Vertex v) const {
        return euler_tour_[v];
    }

    template<typename T>
    void SortVertex(vector<T> &A){
        assert(A.size() == n);
        vector<T> sub(n);
        for(int i = 0; i < n; ++i){
            sub[PreOrder(i)] = A[i];
        }
        swap(A, sub);
    }

    int operator[](Vertex v){
        return PreOrder(v);
    }

    const int operator[](Vertex v) const {
        return PreOrder(v);
    }

    private:
    int dfs(Vertex v, int h, int d){
        euler_tour_[v].first = timer_;
        rev_order_[timer_] = v;
        ++timer_;
        int ret = timer_;
        if(!child[v].empty()){
            int c = child[v].size();
            belong_hp_id_[child[v].front()] = h;
            ret = max(ret, dfs(child[v].front(), h, d));
            for(int i = 1; i < c; ++i){
                int nh = (int)hp_head_.size();
                hp_head_.push_back(child[v][i]);
                hp_depth_.push_back(d + 1);
                belong_hp_id_[child[v][i]] = nh;
                ret = max(ret, dfs(child[v][i], nh, d + 1));
            }
        }
        euler_tour_[v].second = ret;
        return ret;
    }

    Vertex Head(Vertex v) const {
        return hp_head_[belong_hp_id_[v]];
    }

    int PathDepth(Vertex v) const {
        return hp_depth_[belong_hp_id_[v]];
    }

    int Belong(Vertex v) const {
        return belong_hp_id_[v];
    }

    Vertex RevOrder(int idx) const {
        return rev_order_[idx];
    }

    int PreOrder(Vertex v) const {
        return euler_tour_[v].first;
    }

    int PostOrder(Vertex v) const {
        return euler_tour_[v].second;
    }

    Graph<WeightType> &T;
    vector<Vertex> parent;
    vector<vector<Vertex>> child;
    int n, timer_;

    vector<pair<int, int>> euler_tour_;
    vector<Vertex> rev_order_;
    vector<int> depth_;

    vector<Vertex> hp_head_; // 各 heavy path の最も根に近い頂点
    vector<int> hp_depth_; // 各 heavy path の深さ
    vector<int> belong_hp_id_; // 各頂点が属する heavy path の番号
};

#line 2 "Library/Tree/Tree.hpp"

#line 2 "Library/Graph/Graph.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/Graph/Graph.hpp"

using Vertex = int;

template<typename WeightType = int32_t>
struct Edge{
    public:
    Edge() = default;

    Edge(Vertex from_, Vertex to_, WeightType weight_ = 1, int idx_ = -1) :
        from(from_), to(to_), cost(weight_), idx(idx_){}
    
    bool operator<(const Edge<WeightType> &e) const {return cost < e.cost;}

    operator int() const {return to;}

    Vertex from, to;
    WeightType cost;
    int idx;
};

template<typename WeightType = int32_t>
class Graph{
    public:
    Graph() = default;

    Graph(int V) : edge_size_(0), adjacent_list_(V){}
    
    inline void AddUndirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
        adjacent_list_[v].push_back(Edge<WeightType>(v, u, w, idx));
    }
    
    inline void AddDirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
    }

    inline size_t VertexSize() const {
        return adjacent_list_.size();
    }

    inline size_t EdgeSize() const {
        return edge_size_;
    }

    inline vector<Edge<WeightType>> &operator[](const Vertex v){
        return adjacent_list_[v];
    }

    inline const vector<Edge<WeightType>> &operator[](const Vertex v) const {
        return adjacent_list_[v];
    }
    
    private:
    size_t edge_size_;
    vector<vector<Edge<WeightType>>> adjacent_list_;
};

template<typename WeightType = int32_t>
Graph<WeightType> InputGraph(int N, int M, int padding = -1, bool weighted = false, bool directed = false){
    Graph<WeightType> G(N);
    for(int i = 0; i < M; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        if(directed) G.AddDirectedEdge(u, v, w);
        else G.AddUndirectedEdge(u, v, w);
    }
    return G;
}
#line 4 "Library/Tree/Tree.hpp"

template<typename WeightType = int32_t>
Graph<WeightType> InputTree(int V, int padding = -1, bool weighted = false){
    Graph<WeightType> G(V);
    for(int i = 0; i < V - 1; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        G.AddUndirectedEdge(u, v, w);
    }
    return G;
}

template<typename WeightType = int32_t>
Graph<WeightType> InputRootedTreeChild(int V, int padding = -1){
    Graph<WeightType> G(V);
    for(Vertex u = 0; u < V; ++u){
        int k; cin >> k;
        for(int i = 0; i < k; ++i){
            Vertex v; cin >> v, v += padding;
            G.AddUndirectedEdge(u, v);
        }
    }
    return G;
}

template<typename WeightType = int32_t>
Graph<WeightType> InputRootedTreeParent(int V, int padding = -1){
    Graph<WeightType> G(V);
    for(Vertex u = 1; u < V; ++u){
        Vertex v; cin >> v, v += padding;
        G.AddUndirectedEdge(u, v);
    }
    return G;
}

template<typename WeightType = int32_t>
vector<vector<Vertex>> RootedTreeAdjacentList(const Graph<WeightType> &T, const Vertex r = 0){
    int V = T.VertexSize();
    vector<vector<Vertex>> ret(V);
    auto rec = [&](auto &self, Vertex u, Vertex p) -> void {
        for(Vertex v : T[u]){
            if(v == p) continue;
            ret[u].push_back(v);
            self(self, v, u);
        }
    };
    rec(rec, r, -1);
    return ret;
}

template<typename WeightType>
vector<Vertex> CalculateTreeParent(Graph<WeightType> &T, Vertex r = 0){
    int V = T.VertexSize();
    vector<Vertex> ret(V, -1);
    auto rec = [&](auto &self, Vertex u) -> void {
        for(Vertex v : T[u]){
            if(v == ret[u]) continue;
            ret[v] = u;
            self(self, v);
        }
    };
    rec(rec, r);
    return ret;
}

template<typename WeightType>
vector<WeightType> CalculateTreeCost(Graph<WeightType> &T, Vertex r = 0){
    int V = T.VertexSize();
    vector<WeightType> ret(V);
    auto rec = [&](auto &self, Vertex u, Vertex p) -> void {
        for(const Edge<WeightType> &e : T[u]){
            Vertex v = e.to;
            if(v == p) continue;
            ret[v] = e.cost;
            self(self, v, u);
        }
    };
    rec(rec, r, -1);
    return ret;
}

template<typename WeightType>
vector<int> CalculateTreeDepth(Graph<WeightType> &T, Vertex r = 0){
    int V = T.VertexSize();
    vector<int> ret(V, 0);
    auto rec = [&](auto &self, Vertex u, Vertex p, int d) -> void {
        ret[u] = d;
        for(Vertex v : T[u]){
            if(v == p) continue;
            self(self, v, u, d + 1);
        }
    };
    rec(rec, r, -1, 0);
    return ret;
}

template<typename WeightType>
vector<WeightType> CalculateTreeDistance(Graph<WeightType> &T, Vertex r = 0){
    int V = T.VertexSize();
    vector<WeightType> ret(V, WeightType(INF));
    auto rec = [&](auto &self, Vertex u) -> void {
        for(const Edge<WeightType> &e : T[u]){
            if(ret[e.to] > ret[u] + e.cost){
                ret[e.to] = ret[u] + e.cost;
                self(self, e.to);
            }
        }
    };
    ret[r] = 0;
    rec(rec, r);
    return ret;
}

template<typename WeightType>
vector<int> CalculateSubtreeSize(Graph<WeightType> &tree, Vertex r = 0){
    int V = tree.VertexSize();
    vector<int> ret(V, 1);
    auto rec = [&](auto self, Vertex u, Vertex p) -> int {
        for(const int v : tree[u]){
            if(v == p) continue;
            ret[u] += self(self, v, u);
        }
        return ret[u];
    };
    rec(rec, r, -1);
    return ret;
}
#line 2 "Library/Tree/HeavyLightDecomposition.hpp"

struct PathSegment{
    PathSegment() = default;
    Vertex head_vertex;
    Vertex tail_vertex;
    int head_index;
    int tail_index;
    bool highest;
    bool reverse;
    friend ostream &operator<<(ostream &os, const PathSegment &p){
        return os << "# Path (" << p.head_vertex << " -> " << p.tail_vertex << ", " << p.head_index << " -> " << p.tail_index << ", " << boolalpha << p.highest << ", " << p.reverse << ")";
    }
};

template<typename WeightType>
class HeavyLightDecomposition{
    public:
    HeavyLightDecomposition(Graph<WeightType> &tree, Vertex r = 0) :
        T(tree), parent(CalculateTreeParent(tree, r)), child(RootedTreeAdjacentList(tree, r)), n((int)tree.VertexSize()), euler_tour_(n), rev_order_(n), depth_(CalculateTreeDepth(tree, r)), belong_hp_id_(n){
        vector<int> ss = CalculateSubtreeSize(T, r);
        for(int i = 0; i < n; ++i){
            if(child[i].empty()) continue;
            nth_element(child[i].begin(), child[i].begin() + 1, child[i].end(), [&](Vertex i, Vertex j){
                return ss[i] > ss[j];
            });
        }
        hp_head_.push_back(r);
        hp_depth_.push_back(0);
        belong_hp_id_[r] = 0;
        timer_ = 0;
        dfs(r, 0, 0);
    }

    Vertex LowestCommonAncestor(Vertex u, Vertex v) const {
        if(PathDepth(u) < PathDepth(v)) swap(u, v);
        while(PathDepth(u) != PathDepth(v)){
            u = parent[Head(u)];
        }
        while(Belong(u) != Belong(v)){
            u = parent[Head(u)];
            v = parent[Head(v)];
        }
        return depth_[u] < depth_[v] ? u : v;
    }

    Vertex LevelAncestor(Vertex v, int k){
        assert(k <= depth_[v]);
        Vertex ret = v;
        while(1){
            int h = Head(ret);
            int x = depth_[ret] - depth_[h];
            if(k <= x){
                ret = RevOrder(PreOrder(ret) - k);
                break;
            }
            ret = parent[h];
            k -= x + 1;
        }
        return ret;
    }

    int Jump(Vertex u, Vertex v, int k){
        Vertex w = LowestCommonAncestor(u, v);
        int p = depth_[u] - depth_[w], q = depth_[v] - depth_[w];
        if(p + q < k || k < 0) return -1;
        if(k <= p) return LevelAncestor(u, k);
        else return LevelAncestor(v, p + q - k);
    }

    vector<PathSegment> PathQuery(Vertex u, Vertex v){
        vector<PathSegment> ret;
        Vertex lca = LowestCommonAncestor(u, v);
        while(Belong(u) != Belong(lca)){
            PathSegment path;
            Vertex h = Head(u);
            path.head_vertex = h, path.tail_vertex = u;
            path.head_index = PreOrder(h), path.tail_index = PreOrder(u) + 1;
            path.highest = false, path.reverse = true;
            ret.push_back(path);
            u = parent[h];
        }
        if(u != lca){
            PathSegment path;
            path.head_vertex = lca, path.tail_vertex = u;
            path.head_index = PreOrder(lca), path.tail_index = PreOrder(u) + 1;
            path.highest = true, path.reverse = true;
            ret.push_back(path);
        }
        int size = ret.size();
        while(Belong(v) != Belong(lca)){
            PathSegment path;
            Vertex h = Head(v);
            path.head_vertex = h, path.tail_vertex = v;
            path.head_index = PreOrder(h), path.tail_index = PreOrder(v) + 1;
            path.highest = false, path.reverse = false;
            ret.push_back(path);
            v = parent[h];
        }
        if(v != lca){
            PathSegment path;
            path.head_vertex = lca, path.tail_vertex = v;
            path.head_index = PreOrder(lca), path.tail_index = PreOrder(v) + 1;
            path.highest = true, path.reverse = false;
            ret.push_back(path);
        }
        if(u == lca && v == lca){
            PathSegment path;
            path.head_vertex = path.tail_vertex = lca;
            path.head_index = PreOrder(lca), path.tail_index = PreOrder(lca) + 1;
            path.highest = true, path.reverse = false;
            ret.push_back(path);
        }
        reverse(ret.begin() + size, ret.end());
        return ret;
    }

    pair<int, int> SubtreeQuery(Vertex v) const {
        return euler_tour_[v];
    }

    template<typename T>
    void SortVertex(vector<T> &A){
        assert(A.size() == n);
        vector<T> sub(n);
        for(int i = 0; i < n; ++i){
            sub[PreOrder(i)] = A[i];
        }
        swap(A, sub);
    }

    int operator[](Vertex v){
        return PreOrder(v);
    }

    const int operator[](Vertex v) const {
        return PreOrder(v);
    }

    private:
    int dfs(Vertex v, int h, int d){
        euler_tour_[v].first = timer_;
        rev_order_[timer_] = v;
        ++timer_;
        int ret = timer_;
        if(!child[v].empty()){
            int c = child[v].size();
            belong_hp_id_[child[v].front()] = h;
            ret = max(ret, dfs(child[v].front(), h, d));
            for(int i = 1; i < c; ++i){
                int nh = (int)hp_head_.size();
                hp_head_.push_back(child[v][i]);
                hp_depth_.push_back(d + 1);
                belong_hp_id_[child[v][i]] = nh;
                ret = max(ret, dfs(child[v][i], nh, d + 1));
            }
        }
        euler_tour_[v].second = ret;
        return ret;
    }

    Vertex Head(Vertex v) const {
        return hp_head_[belong_hp_id_[v]];
    }

    int PathDepth(Vertex v) const {
        return hp_depth_[belong_hp_id_[v]];
    }

    int Belong(Vertex v) const {
        return belong_hp_id_[v];
    }

    Vertex RevOrder(int idx) const {
        return rev_order_[idx];
    }

    int PreOrder(Vertex v) const {
        return euler_tour_[v].first;
    }

    int PostOrder(Vertex v) const {
        return euler_tour_[v].second;
    }

    Graph<WeightType> &T;
    vector<Vertex> parent;
    vector<vector<Vertex>> child;
    int n, timer_;

    vector<pair<int, int>> euler_tour_;
    vector<Vertex> rev_order_;
    vector<int> depth_;

    vector<Vertex> hp_head_; // 各 heavy path の最も根に近い頂点
    vector<int> hp_depth_; // 各 heavy path の深さ
    vector<int> belong_hp_id_; // 各頂点が属する heavy path の番号
};

Back to top page