Heavy-light Decomposition (tree/hld.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-09-25 11:45:13+07:00
• Include: #include "tree/hld.hpp"

Description

Heavy-light decomposition decomposes a tree into heavy/light edges such that each path from a vertex to root goes through $\mathcal O(\log n)$ light edge. This allows efficient path queries.

Operations

• HLD(G &g, int root = 0)
  • Decompose tree into heavy/light paths
  • Time complexity: $\mathcal O(n)$
• int lca(int u, int v)
  • Returns the lowest common ancestor of u and v
  • Time complexity: $\mathcal O(\log n)$
• int dist(int u, int v)
  • Returns the length of the path from u to v
  • Time complexity: $\mathcal O(\log n)$
• vector<pair<int, int>> path(int v, int p, bool es = false)
  • Returns the intervals representing the path from v to p, es == true excludes p from the interval
  • Time complexity: $\mathcal O(\log n)$
• pair<int, int> subtree(int v)
  • Returns the interval representing the subtree of v
  • Time complexity: $\mathcal O(1)$

Reference

• CP Algorithms
• tko919
• Easiest HLD with subtree queries

Required by

• Virtual Tree (tree/virtual_tree.hpp)

Verified with

• test/yosupo/tree/lca_hld.test.cpp
• test/yosupo/tree/vertex_add_path_sum_hld.test.cpp

Code

#pragma once

struct HLD {
    int n;
    vector<int> in, par, dep, out, hs;

    template<class G>
    HLD(G &g, int root = 0) :
        n((int)g.size()), in(n), par(n), dep(n), out(n), hs(n) {
        hs[root] = root;
        dfs_sz(g, root);
        dfs_hld(g, root);
        assert(time == n);
    }

    int lca(int u, int v) const {
        assert(0 <= u && u < n && 0 <= v && v < n);
        for (;; v = par[hs[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (hs[u] == hs[v]) return u;
        }
    }
    int dist(int u, int v) const {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    auto path(int v, int p, bool es = 0) const {
        assert(in[p] <= in[v] && out[v] <= out[p]);
        vector<pair<int, int>> res;
        for (; hs[v] != hs[p]; v = par[hs[v]])
            res.emplace_back(in[hs[v]], in[v] + 1);
        res.emplace_back(in[p] + es, in[v] + 1);
        return res;
    }
    pair<int, int> subtree(int v) const {
        assert(0 <= v && v < n);
        return {in[v], out[v]};
    }
    int operator[](int v) { return in[v]; }
    int operator()(int v) { return out[v]; }

  private:
    int time = 0;
    template<class G> int dfs_sz(G &g, int v, int p = -1) {
        par[v] = p;
        int sz = 1, mx = 0;
        for (auto &c : g[v]) {
            if (c == p) continue;
            dep[c] = dep[v] + 1;
            int s = dfs_sz(g, c, v);
            sz += s;
            if (g[v][0] == p || mx < s) mx = s, swap(g[v][0], c);
        }
        return sz;
    }
    template<class G> void dfs_hld(G &g, int v, int p = -1) {
        in[v] = time++;
        for (auto c : g[v]) {
            if (c == p) continue;
            hs[c] = (c == g[v][0] ? hs[v] : c);
            dfs_hld(g, c, v);
        }
        out[v] = time;
    }
};

#line 2 "tree/hld.hpp"

struct HLD {
    int n;
    vector<int> in, par, dep, out, hs;

    template<class G>
    HLD(G &g, int root = 0) :
        n((int)g.size()), in(n), par(n), dep(n), out(n), hs(n) {
        hs[root] = root;
        dfs_sz(g, root);
        dfs_hld(g, root);
        assert(time == n);
    }

    int lca(int u, int v) const {
        assert(0 <= u && u < n && 0 <= v && v < n);
        for (;; v = par[hs[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (hs[u] == hs[v]) return u;
        }
    }
    int dist(int u, int v) const {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    auto path(int v, int p, bool es = 0) const {
        assert(in[p] <= in[v] && out[v] <= out[p]);
        vector<pair<int, int>> res;
        for (; hs[v] != hs[p]; v = par[hs[v]])
            res.emplace_back(in[hs[v]], in[v] + 1);
        res.emplace_back(in[p] + es, in[v] + 1);
        return res;
    }
    pair<int, int> subtree(int v) const {
        assert(0 <= v && v < n);
        return {in[v], out[v]};
    }
    int operator[](int v) { return in[v]; }
    int operator()(int v) { return out[v]; }

  private:
    int time = 0;
    template<class G> int dfs_sz(G &g, int v, int p = -1) {
        par[v] = p;
        int sz = 1, mx = 0;
        for (auto &c : g[v]) {
            if (c == p) continue;
            dep[c] = dep[v] + 1;
            int s = dfs_sz(g, c, v);
            sz += s;
            if (g[v][0] == p || mx < s) mx = s, swap(g[v][0], c);
        }
        return sz;
    }
    template<class G> void dfs_hld(G &g, int v, int p = -1) {
        in[v] = time++;
        for (auto c : g[v]) {
            if (c == p) continue;
            hs[c] = (c == g[v][0] ? hs[v] : c);
            dfs_hld(g, c, v);
        }
        out[v] = time;
    }
};

Back to top page