Heavy-Light Decomposition
(tree/hld.hpp)

• View this file on GitHub
• Last update: 2024-01-07 23:25:49+09:00
• Include: #include "tree/hld.hpp"

Description

HL 分解 (重軽分解) は，木をいくつかのパスに分解する手法である．分解されたパスからなる木は高さが高々 $O(\log n)$ になる．列に対するクエリを処理するデータ構造を用いて各パスを管理することにより，木上のパスクエリを高速に処理することができる．

空間計算量: $O(n)$

Operations

update および fold の時間計算量を $f(n)$ とする

• HLD(vector<vector<int>> G, bool edge)
  • 木 G を HL 分解する．edge == true ならクエリは辺に対して実行される．
  • 時間計算量: $O(n)$
• void update(int v, T x, F update)
  • 頂点 $v$ に対して update(x) を実行する
  • 時間計算量: $O(f(n) \log n)$
• void update_edge(int u, int v, T x, F update)
  • 辺 $(u, v)$ に対して update(x) を実行する
  • 時間計算量: $O(f(n) \log n)$
• void update(int u, int v, T x, F update)
  • $uv$ パス上の頂点/辺に対して update(x) を実行する．
  • 時間計算量: $O(f(n) \log n)$
• T path_fold(int u, int v, F fold)
  • $uv$ パス上の頂点/辺に対して fold() を実行する．
  • 時間計算量: $O(f(n) \log n)$
• T path_fold(int u, int v, F fold, Flip flip)
  • $uv$ パス上の頂点/辺に対して fold() を実行する．値が非可換なら，左から積をとったときと右から積をとったときの値を入れ替える flip 関数を与える必要がある．
  • 時間計算量: $O(f(n) \log n)$
• T subtree_fold(int v, F fold)
  • 頂点 $v$ を根とする部分木の頂点/辺に対して fold() を実行する．
  • 時間計算量: $O(f(n))$
• int lca(int u, int v)
  • 頂点 $u$ と頂点 $v$ の最小共通祖先を返す
  • 時間計算量: $O(\log n)$
• int dist(int u, int v)
  • $uv$ 間の距離を計算する
  • 時間計算量: $O(\log n)$

Reference

• Heavy-Light Decomposition
• Heavy-light decomposition
• Easiest HLD with subtree queries

Verified with

• test/yosupo/vertex_add_subtree_sum.hld.test.cpp
• test/yosupo/vertex_set_path_composite.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

template <typename M>
class HLD {
    using T = M::T;

   public:
    HLD() = default;
    HLD(const std::vector<std::vector<int>>& G, bool edge)
        : G(G),
          size(G.size()),
          depth(G.size()),
          par(G.size(), -1),
          in(G.size()),
          out(G.size()),
          head(G.size()),
          heavy(G.size(), -1),
          edge(edge) {
        dfs(0);
        decompose(0, 0);
    }

    template <typename F>
    void update(int v, const T& x, const F& f) const {
        f(in[v], x);
    }

    template <typename F>
    void update_edge(int u, int v, const T& x, const F& f) const {
        if (in[u] > in[v]) std::swap(u, v);
        f(in[v], x);
    }

    template <typename E, typename F>
    void update(int u, int v, const E& x, const F& f) const {
        while (head[u] != head[v]) {
            if (in[head[u]] > in[head[v]]) std::swap(u, v);
            f(in[head[v]], in[v] + 1, x);
            v = par[head[v]];
        }
        if (in[u] > in[v]) std::swap(u, v);
        f(in[u] + edge, in[v] + 1, x);
    }

    template <typename F, typename Flip>
    T path_fold(int u, int v, const F& f, const Flip& flip) const {
        bool flipped = false;
        T resu = M::id(), resv = M::id();
        while (head[u] != head[v]) {
            if (in[head[u]] > in[head[v]]) {
                std::swap(u, v);
                std::swap(resu, resv);
                flipped ^= true;
            }
            T val = f(in[head[v]], in[v] + 1);
            resv = M::op(val, resv);
            v = par[head[v]];
        }
        if (in[u] > in[v]) {
            std::swap(u, v);
            std::swap(resu, resv);
            flipped ^= true;
        }
        T val = f(in[u] + edge, in[v] + 1);
        resv = M::op(val, resv);
        resv = M::op(flip(resu), resv);
        if (flipped) {
            resv = flip(resv);
        }
        return resv;
    }

    template <typename F>
    T path_fold(int u, int v, const F& f) const {
        return path_fold(u, v, f, [&](auto& v) { return v; });
    }

    template <typename F>
    T subtree_fold(int v, const F& f) const {
        return f(in[v] + edge, out[v]);
    }

    int lca(int u, int v) const {
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }

    int dist(int u, int v) const {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }

   private:
    std::vector<std::vector<int>> G;
    std::vector<int> size, depth, par, in, out, head, heavy;
    bool edge;
    int cur_pos = 0;

    void dfs(int v) {
        size[v] = 1;
        int max_size = 0;
        for (int c : G[v]) {
            if (c == par[v]) continue;
            par[c] = v;
            depth[c] = depth[v] + 1;
            dfs(c);
            size[v] += size[c];
            if (size[c] > max_size) {
                max_size = size[c];
                heavy[v] = c;
            }
        }
    }

    void decompose(int v, int h) {
        head[v] = h;
        in[v] = cur_pos++;
        if (heavy[v] != -1) decompose(heavy[v], h);
        for (int c : G[v]) {
            if (c != par[v] && c != heavy[v]) decompose(c, c);
        }
        out[v] = cur_pos;
    }
};

#line 2 "tree/hld.hpp"
#include <algorithm>
#include <vector>

template <typename M>
class HLD {
    using T = M::T;

   public:
    HLD() = default;
    HLD(const std::vector<std::vector<int>>& G, bool edge)
        : G(G),
          size(G.size()),
          depth(G.size()),
          par(G.size(), -1),
          in(G.size()),
          out(G.size()),
          head(G.size()),
          heavy(G.size(), -1),
          edge(edge) {
        dfs(0);
        decompose(0, 0);
    }

    template <typename F>
    void update(int v, const T& x, const F& f) const {
        f(in[v], x);
    }

    template <typename F>
    void update_edge(int u, int v, const T& x, const F& f) const {
        if (in[u] > in[v]) std::swap(u, v);
        f(in[v], x);
    }

    template <typename E, typename F>
    void update(int u, int v, const E& x, const F& f) const {
        while (head[u] != head[v]) {
            if (in[head[u]] > in[head[v]]) std::swap(u, v);
            f(in[head[v]], in[v] + 1, x);
            v = par[head[v]];
        }
        if (in[u] > in[v]) std::swap(u, v);
        f(in[u] + edge, in[v] + 1, x);
    }

    template <typename F, typename Flip>
    T path_fold(int u, int v, const F& f, const Flip& flip) const {
        bool flipped = false;
        T resu = M::id(), resv = M::id();
        while (head[u] != head[v]) {
            if (in[head[u]] > in[head[v]]) {
                std::swap(u, v);
                std::swap(resu, resv);
                flipped ^= true;
            }
            T val = f(in[head[v]], in[v] + 1);
            resv = M::op(val, resv);
            v = par[head[v]];
        }
        if (in[u] > in[v]) {
            std::swap(u, v);
            std::swap(resu, resv);
            flipped ^= true;
        }
        T val = f(in[u] + edge, in[v] + 1);
        resv = M::op(val, resv);
        resv = M::op(flip(resu), resv);
        if (flipped) {
            resv = flip(resv);
        }
        return resv;
    }

    template <typename F>
    T path_fold(int u, int v, const F& f) const {
        return path_fold(u, v, f, [&](auto& v) { return v; });
    }

    template <typename F>
    T subtree_fold(int v, const F& f) const {
        return f(in[v] + edge, out[v]);
    }

    int lca(int u, int v) const {
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }

    int dist(int u, int v) const {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }

   private:
    std::vector<std::vector<int>> G;
    std::vector<int> size, depth, par, in, out, head, heavy;
    bool edge;
    int cur_pos = 0;

    void dfs(int v) {
        size[v] = 1;
        int max_size = 0;
        for (int c : G[v]) {
            if (c == par[v]) continue;
            par[c] = v;
            depth[c] = depth[v] + 1;
            dfs(c);
            size[v] += size[c];
            if (size[c] > max_size) {
                max_size = size[c];
                heavy[v] = c;
            }
        }
    }

    void decompose(int v, int h) {
        head[v] = h;
        in[v] = cur_pos++;
        if (heavy[v] != -1) decompose(heavy[v], h);
        for (int c : G[v]) {
            if (c != par[v] && c != heavy[v]) decompose(c, c);
        }
        out[v] = cur_pos;
    }
};

Back to top page