src/graph/hld.hpp

View this file on GitHub
Last update: 2025-10-03 20:06:51+08:00
Include: #include "src/graph/hld.hpp"

Depends on

src/ds/sgt.hpp

Verified with

Code

#include "../ds/sgt.hpp"
struct HLD {
  struct Info {
    ll data = 0;
    friend Info operator+(Info lhs, Info rhs) { return {lhs.data + rhs.data}; }
  };
  SegTree<Info> sgt = 0;
  int n, cur_dfn;
  vector<int> fa, dep, siz, hson;
  vector<int> dfn, rdfn, top;
  vector<vector<int>> G;
  HLD(int n)
      : n(n), fa(n, -1), dep(n), siz(n), hson(n, -1), dfn(n), rdfn(n), top(n),
        G(n) {}
  void adde(int u, int v) { G[u].PUSHB(v), G[v].PUSHB(u); }
  void init_dfn(int root) { cur_dfn = 0, dfs1(root, -1), dfs2(root, root); }
  void init_sgt(const vector<int>& a) {
    vector<Info> b(n);
    for (int i = 0; i < n; i++) b[dfn[i]].data = a[i];
    sgt = SegTree(b);
  }
  int lca(int u, int v) const {
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) swap(u, v);
      u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
  }
  void add(int p, int x) {
    Info qry = sgt.sum(dfn[p], dfn[p] + 1);
    qry.data += x;
    sgt.set(dfn[p], qry);
  }
  ll query(int u, int v) {
    Info ret;
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) swap(u, v);
      ret = ret + sgt.sum(dfn[top[u]], dfn[u] + 1);
      u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) swap(u, v);
    ret = ret + sgt.sum(dfn[u], dfn[v] + 1);
    return ret.data;
  }

 private:
  void dfs1(int u, int fa_) {
    fa[u] = fa_;
    siz[u] = 1;
    for (int v : G[u]) {
      if (v == fa_) continue;
      dep[v] = dep[u] + 1;
      dfs1(v, u);
      siz[u] += siz[v];
      if (hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v;
    }
  }
  void dfs2(int u, int top_) {
    dfn[u] = cur_dfn;
    rdfn[cur_dfn++] = u;
    top[u] = top_;
    if (hson[u] != -1) dfs2(hson[u], top_);
    for (int v : G[u])
      if (v != fa[u] && v != hson[u]) dfs2(v, v);
  }
};

#line 1 "src/ds/sgt.hpp"
template <typename Info>
struct SegTree {
  int n, _pos, _l, _r;
  Info _node;
  vector<Info> tree;
  SegTree(int n) : n(n), tree(4 * n) {}
  SegTree(const vector<Info>& a) : SegTree(a.size()) { build(1, 0, n, a); }
  void set(int pos, Info node) { _pos = pos, _node = node, set(1, 0, n); }
  Info sum(int l, int r) { return _l = l, _r = r, sum(1, 0, n); }

 private:
  void build(int p, int pl, int pr, const vector<Info>& a) {
    if (pr - pl == 1) return tree[p] = a[pl], void();
    int ls = p * 2, rs = p * 2 + 1, mid = pl + (pr - pl) / 2;
    build(ls, pl, mid, a), build(rs, mid, pr, a);
    tree[p] = tree[ls] + tree[rs];
  }
  void set(int p, int pl, int pr) {
    if (pr - pl == 1) return tree[p] = _node, void();
    int ls = p * 2, rs = p * 2 + 1, mid = pl + (pr - pl) / 2;
    _pos < mid ? set(ls, pl, mid) : set(rs, mid, pr);
    tree[p] = tree[ls] + tree[rs];
  }
  Info sum(int p, int pl, int pr) {
    if (_r <= pl || pr <= _l) return {};
    if (_l <= pl && pr <= _r) return tree[p];
    int ls = p * 2, rs = p * 2 + 1, mid = pl + (pr - pl) / 2;
    return sum(ls, pl, mid) + sum(rs, mid, pr);
  }
};
struct Info {
  int data = 2e9;
  friend Info operator+(const Info& lhs, const Info& rhs) {
    return {min(lhs.data, rhs.data)};
  }
};
#line 2 "src/graph/hld.hpp"
struct HLD {
  struct Info {
    ll data = 0;
    friend Info operator+(Info lhs, Info rhs) { return {lhs.data + rhs.data}; }
  };
  SegTree<Info> sgt = 0;
  int n, cur_dfn;
  vector<int> fa, dep, siz, hson;
  vector<int> dfn, rdfn, top;
  vector<vector<int>> G;
  HLD(int n)
      : n(n), fa(n, -1), dep(n), siz(n), hson(n, -1), dfn(n), rdfn(n), top(n),
        G(n) {}
  void adde(int u, int v) { G[u].PUSHB(v), G[v].PUSHB(u); }
  void init_dfn(int root) { cur_dfn = 0, dfs1(root, -1), dfs2(root, root); }
  void init_sgt(const vector<int>& a) {
    vector<Info> b(n);
    for (int i = 0; i < n; i++) b[dfn[i]].data = a[i];
    sgt = SegTree(b);
  }
  int lca(int u, int v) const {
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) swap(u, v);
      u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
  }
  void add(int p, int x) {
    Info qry = sgt.sum(dfn[p], dfn[p] + 1);
    qry.data += x;
    sgt.set(dfn[p], qry);
  }
  ll query(int u, int v) {
    Info ret;
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) swap(u, v);
      ret = ret + sgt.sum(dfn[top[u]], dfn[u] + 1);
      u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) swap(u, v);
    ret = ret + sgt.sum(dfn[u], dfn[v] + 1);
    return ret.data;
  }

 private:
  void dfs1(int u, int fa_) {
    fa[u] = fa_;
    siz[u] = 1;
    for (int v : G[u]) {
      if (v == fa_) continue;
      dep[v] = dep[u] + 1;
      dfs1(v, u);
      siz[u] += siz[v];
      if (hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v;
    }
  }
  void dfs2(int u, int top_) {
    dfn[u] = cur_dfn;
    rdfn[cur_dfn++] = u;
    top[u] = top_;
    if (hson[u] != -1) dfs2(hson[u], top_);
    for (int v : G[u])
      if (v != fa[u] && v != hson[u]) dfs2(v, v);
  }
};