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

• View this file on GitHub
• Last update: 2025-03-23 01:11:28+09:00
• Include: #include "graph/tree/heavy_light_decomposition.hpp"
• Link: https://ngtkana.hatenablog.com/entry/2024/06/24/200138

木に関する部分木クエリ、パスクエリを処理するためのデータ構造。

使い方

HaruiLib::HLD hld(N);

for (int i=0; i<N-1; i++) {
  int u, v; cin >> u >> v;
  hld.graph.add_edge(u,v);
  hld.graph.add_edge(v,u);
}

hld.build();

みたいに構築したあと、

int a,b; cin >> a >> b;
HaruiLib::Path path = hld.get_path(a,b);

ll sum = 0;
for(HaruiLib::Interval intv: path) {
  sum += seg.prod(intv.top_id, intv.bottom_id + 1);
}

のように、id上でセグ木などの列に対するアルゴリズムを使っていく流れが基本だと思われる。

他にも、

• 辺属性なら子側の頂点に持たせるほうがいい
• 辺属性を考えるときはLCAの頂点に注意する

みたいな色々考えておくことがある。

コンストラクタ

HLD (int N)

N :　頂点の数。

(HLD hld(20);などして構築したあと、hld.graph.add_edge(0,1); などして木の情報を与える。)

build

void build(int root=0)

rootを根とした木のHeavy-Light Decompositionを実行する。

lca

int lca(int u, int v)

uとvの最小共通祖先(LCA)を求める。

get_path

Path get_path(int u, int v)

頂点uから頂点vまでのパスを返す。パスはHeavy-Edgeで繋がれた区間(Interval)のvectorとして表される。

ここで、 using Path = std::vector<Interval>として定義されていて、Intervalは

struct Interval {
  // top_id : interval のもっとも根に近い頂点のid
  // bottom_id : interval のもっとも葉に近い頂点のid
  // last : LCAを含む interval であるかどうか
  // reverse : from → to と top → bottomが逆向きかどうか
  int top_id, bottom_id;
  bool last;
  bool reverse;

  Interval(int _top_id, int _bottom_id, bool _last, bool _reverse) : top_id(_top_id), bottom_id(_bottom_id), last(_last), reverse(_reverse) {

  }
};

として定義されている。

subtree_query

std::pair<int,int> subtree_query(int r)

頂点rの部分木(rも含む)の頂点列を表すid上の区間 $[id[r], id2[r])$ を返す。

計算量

• $O(1)$

Depends on

• graph/graph_template.hpp

Verified with

• test/verify/yosupo-vertex-add-path-sum.test.cpp
• test/verify/yosupo-vertex-add-subtree-sum.test.cpp
• test/verify/yosupo-vertex-set-path-composite.test.cpp

Code

#ifndef HARUILIB_GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP
#define HARUILIB_GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP

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

#include "graph/graph_template.hpp"

namespace HaruiLib {
  // cf : https://ngtkana.hatenablog.com/entry/2024/06/24/200138
  struct Interval {
    // top_id : interval のもっとも根に近い頂点のid
    // bottom_id : interval のもっとも葉に近い頂点のid
    // last : LCAを含む interval であるかどうか
    // reverse : from → to と top → bottomが逆向きかどうか
    int top_id, bottom_id;
    bool last;
    bool reverse;
  
    Interval(int _top_id, int _bottom_id, bool _last, bool _reverse) : top_id(_top_id), bottom_id(_bottom_id), last(_last), reverse(_reverse) {
  
    }
  };
  
  using Path = std::vector<Interval>;
  
  /*
  木をいくつかのパスに分けるアルゴリズム。
  うまくDFSしてパスに分けると、同じパスの中でidが連続するので、一つのパスの中ではセグメント木などの列に対してのアルゴリズムが使えるようになる。
  
  頂点属性の問題はかんたん。
  辺属性の問題は、辺の子側の頂点にその情報をもたせて管理するといい。 そのときはLCAに注意する。
  */
  struct HLD {
  private:
    bool is_built = false;
  public:
    //vector<vector<int>>children;
    std::vector<int> parent;
    std::vector<int> id; // id[v] := 頂点vがdfs順で何番目にあるか。 HLDで分割したパスの中では、深さが浅い方から深い方へidが連続して増えていく。
    std::vector<int> id2;
    std::vector<int> head; // head[v] := 頂点vが所属する分割されたパスの、一番根に近い頂点。
    std::vector<int> depth; // depth[v] := 頂点vの深さ
    Graph<int> graph;
  
    HLD (int N) : parent(std::vector<int>(N, -1)), id(std::vector<int>(N)), id2(std::vector<int>(N)), head(std::vector<int>(N)), depth(std::vector<int>(N)), graph(N) {}
  
    void build(int root=0) {
      dfs_sz(root);
      int k = 0; dfs_hld(root, k);
      is_built = true;
    }
  
    int dfs_sz(int v) {
      int ret = 1, mx_sz = 0;
      for (Edge<int>& nxt : graph[v]) {
        if (nxt.to == parent[v]) continue;
  
        parent[nxt.to] = v;
        depth[nxt.to] = depth[v] + 1;
        int sz = dfs_sz(nxt.to);
        ret += sz;
        if (mx_sz < sz) {
          mx_sz = sz;
          std::swap(graph[v][0], nxt);
        }
      }
  
      return ret;
    }
  
    void dfs_hld(int v, int& k) {
      id[v] = k; k++;
      for (Edge e : graph[v]) {
        if (e.to == parent[v]) continue;
  
        // 今見ている辺が最大連結成分方向への辺なら,head[e.to] = head[v]
        // そうでないなら、head[e.to] = e.to;
        head[e.to] = (e == graph[v][0] ? head[v] : e.to);
        dfs_hld(e.to, k);
      }
      id2[v] = k;
    }
  
    int lca(int u, int v) {
      assert(is_built);
      while (true) {
        if (id[u] > id[v]) std::swap(u, v);
        if (head[u] == head[v]) return u;
  
        v = parent[head[v]];
      }
    }
  
    Path get_path(int u, int v) {
      assert(is_built);
      Path upath, vpath;
  
      while (head[u] != head[v]) {
  
        // ちなみにu,vのdepthの大小関係は変わり続けることもある。
        // 10 → 12など。
  
        // v's head is deeper
        if (depth[head[v]] >= depth[head[u]]) {
          assert(depth[head[v]] >= depth[head[u]]);
          /*
            /   : heavy edge
           .... : light edge
  
              head[u]
                 /
                /...
               u  ...
              /   head[v]
             /       \
            /         \
           /           v
          */
  
          // u→v なのでreverse=false
          vpath.emplace_back(id[head[v]], id[v], false, false);
          v = parent[head[v]];
        }
  
        // u's head is deeper
        else if (depth[head[v]] < depth[head[u]]) {
          /*
            /   : heavy edge
           .... : light edge
  
              head[v]
                 /
                /...
               v  ...
              /   head[u]
             /       \
            /         \
           /           u
          */
  
          //
          upath.emplace_back(id[head[u]], id[u], false, true);
          u = parent[head[u]];
        }
      }
  
      // v is deeper
      /*
         u
        /
       /  ←↓
      /
     v
  
      */
      if (depth[v] > depth[u]) {
        upath.emplace_back(id[u], id[v], true, false);
      }
  
      // u is deeper
      /*
         v
        /
       /  →↑
      /
     u
  
      */
      else {
        upath.emplace_back(id[v], id[u], true, true);
      }
      Path retpath = upath;
      std::reverse(vpath.begin(), vpath.end());
      for (Interval path : vpath) retpath.push_back(path);
  
      return retpath;
    }
  
    std::pair<int,int> subtree_query(int r) {
      assert(r < int(id.size()));
      return std::make_pair(id[r], id2[r]);
    }
  
  };

}
#endif // HARUILIB_GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP

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



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

#line 1 "graph/graph_template.hpp"



#line 5 "graph/graph_template.hpp"

template <typename T>
struct Edge {
  int from; int to;
  T cost;

  // default constructor
  Edge () : from(-1), to(-1), cost(T(0)) {}

  Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}

  // unweighted
  Edge(int _from, int _to) : from(_from), to(_to), cost(T(1)) {}

  bool operator==(const Edge& rhs) const {
    return from == rhs.from && to == rhs.to && cost == rhs.cost;
  }

  bool operator<(const Edge& rhs) const {
    return cost < rhs.cost;
  }
  
  bool operator>(const Edge& rhs) const {
    return cost > rhs.cost;
  }

};


template <typename T>
struct Graph : std::vector<std::vector<Edge<T>>> {

  using std::vector<std::vector<Edge<T>>>::vector; // inherit constructors

  void add_edge(int i, Edge<T> e) {
    (*this)[i].push_back(e);
  }

  void add_edge(Edge<T> e) {
    (*this)[e.from].push_back(e);
  }

  // weighted
  void add_edge(int _from, int _to, T _cost) {
    (*this)[_from].push_back(Edge(_from, _to, _cost));
  }

  // unweighted
  void add_edge(int _from, int _to) {
    (*this)[_from].push_back(Edge(_from, _to, T(1)));
  }

};


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

namespace HaruiLib {
  // cf : https://ngtkana.hatenablog.com/entry/2024/06/24/200138
  struct Interval {
    // top_id : interval のもっとも根に近い頂点のid
    // bottom_id : interval のもっとも葉に近い頂点のid
    // last : LCAを含む interval であるかどうか
    // reverse : from → to と top → bottomが逆向きかどうか
    int top_id, bottom_id;
    bool last;
    bool reverse;
  
    Interval(int _top_id, int _bottom_id, bool _last, bool _reverse) : top_id(_top_id), bottom_id(_bottom_id), last(_last), reverse(_reverse) {
  
    }
  };
  
  using Path = std::vector<Interval>;
  
  /*
  木をいくつかのパスに分けるアルゴリズム。
  うまくDFSしてパスに分けると、同じパスの中でidが連続するので、一つのパスの中ではセグメント木などの列に対してのアルゴリズムが使えるようになる。
  
  頂点属性の問題はかんたん。
  辺属性の問題は、辺の子側の頂点にその情報をもたせて管理するといい。 そのときはLCAに注意する。
  */
  struct HLD {
  private:
    bool is_built = false;
  public:
    //vector<vector<int>>children;
    std::vector<int> parent;
    std::vector<int> id; // id[v] := 頂点vがdfs順で何番目にあるか。 HLDで分割したパスの中では、深さが浅い方から深い方へidが連続して増えていく。
    std::vector<int> id2;
    std::vector<int> head; // head[v] := 頂点vが所属する分割されたパスの、一番根に近い頂点。
    std::vector<int> depth; // depth[v] := 頂点vの深さ
    Graph<int> graph;
  
    HLD (int N) : parent(std::vector<int>(N, -1)), id(std::vector<int>(N)), id2(std::vector<int>(N)), head(std::vector<int>(N)), depth(std::vector<int>(N)), graph(N) {}
  
    void build(int root=0) {
      dfs_sz(root);
      int k = 0; dfs_hld(root, k);
      is_built = true;
    }
  
    int dfs_sz(int v) {
      int ret = 1, mx_sz = 0;
      for (Edge<int>& nxt : graph[v]) {
        if (nxt.to == parent[v]) continue;
  
        parent[nxt.to] = v;
        depth[nxt.to] = depth[v] + 1;
        int sz = dfs_sz(nxt.to);
        ret += sz;
        if (mx_sz < sz) {
          mx_sz = sz;
          std::swap(graph[v][0], nxt);
        }
      }
  
      return ret;
    }
  
    void dfs_hld(int v, int& k) {
      id[v] = k; k++;
      for (Edge e : graph[v]) {
        if (e.to == parent[v]) continue;
  
        // 今見ている辺が最大連結成分方向への辺なら,head[e.to] = head[v]
        // そうでないなら、head[e.to] = e.to;
        head[e.to] = (e == graph[v][0] ? head[v] : e.to);
        dfs_hld(e.to, k);
      }
      id2[v] = k;
    }
  
    int lca(int u, int v) {
      assert(is_built);
      while (true) {
        if (id[u] > id[v]) std::swap(u, v);
        if (head[u] == head[v]) return u;
  
        v = parent[head[v]];
      }
    }
  
    Path get_path(int u, int v) {
      assert(is_built);
      Path upath, vpath;
  
      while (head[u] != head[v]) {
  
        // ちなみにu,vのdepthの大小関係は変わり続けることもある。
        // 10 → 12など。
  
        // v's head is deeper
        if (depth[head[v]] >= depth[head[u]]) {
          assert(depth[head[v]] >= depth[head[u]]);
          /*
            /   : heavy edge
           .... : light edge
  
              head[u]
                 /
                /...
               u  ...
              /   head[v]
             /       \
            /         \
           /           v
          */
  
          // u→v なのでreverse=false
          vpath.emplace_back(id[head[v]], id[v], false, false);
          v = parent[head[v]];
        }
  
        // u's head is deeper
        else if (depth[head[v]] < depth[head[u]]) {
          /*
            /   : heavy edge
           .... : light edge
  
              head[v]
                 /
                /...
               v  ...
              /   head[u]
             /       \
            /         \
           /           u
          */
  
          //
          upath.emplace_back(id[head[u]], id[u], false, true);
          u = parent[head[u]];
        }
      }
  
      // v is deeper
      /*
         u
        /
       /  ←↓
      /
     v
  
      */
      if (depth[v] > depth[u]) {
        upath.emplace_back(id[u], id[v], true, false);
      }
  
      // u is deeper
      /*
         v
        /
       /  →↑
      /
     u
  
      */
      else {
        upath.emplace_back(id[v], id[u], true, true);
      }
      Path retpath = upath;
      std::reverse(vpath.begin(), vpath.end());
      for (Interval path : vpath) retpath.push_back(path);
  
      return retpath;
    }
  
    std::pair<int,int> subtree_query(int r) {
      assert(r < int(id.size()));
      return std::make_pair(id[r], id2[r]);
    }
  
  };

}

Back to top page