test/graph/hld1.test.cpp

View this file on GitHub
Last update: 2025-10-03 20:06:51+08:00
Problem: https://judge.yosupo.jp/problem/lca

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;

#include "../../src/graph/hld.hpp"
#include "../../src/misc/read.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), q = read();
  HLD hld(n);
  for (int i = 1; i < n; i++) {
    int p = read();
    hld.adde(i, p);
  }
  hld.init_dfn(0);
  while (q--) {
    int u = read(), v = read();
    cout << hld.lca(u, v) << "\n";
  }
  return 0;
}

#line 1 "test/graph/hld1.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;

#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);
  }
};
#line 1 "src/misc/read.hpp"
#define GC ch = getchar_unlocked()
ll read() {
  ll x = 0, f = 1, GC;
  while (ch < '0' || ch > '9') ch == '-' ? f = -1, GC : GC;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', GC;
  return x * f;
}
#undef GC
#line 10 "test/graph/hld1.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), q = read();
  HLD hld(n);
  for (int i = 1; i < n; i++) {
    int p = read();
    hld.adde(i, p);
  }
  hld.init_dfn(0);
  while (q--) {
    int u = read(), v = read();
    cout << hld.lca(u, v) << "\n";
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	165 ms	86 MB
g++	almost_line_01	AC	167 ms	85 MB
g++	binary_00	AC	318 ms	45 MB
g++	binary_01	AC	318 ms	44 MB
g++	binary_02	AC	318 ms	44 MB
g++	example_00	AC	5 ms	4 MB
g++	line_00	AC	117 ms	99 MB
g++	line_01	AC	132 ms	117 MB
g++	line_02	AC	39 ms	17 MB
g++	line_03	AC	89 ms	109 MB
g++	line_04	AC	67 ms	72 MB
g++	max_line_00	AC	145 ms	126 MB
g++	max_line_01	AC	147 ms	126 MB
g++	max_line_02	AC	147 ms	126 MB
g++	max_random_00	AC	257 ms	45 MB
g++	max_random_01	AC	267 ms	45 MB
g++	max_random_02	AC	254 ms	45 MB
g++	path_graph_root_centroid_00	AC	122 ms	85 MB
g++	path_graph_root_centroid_01	AC	124 ms	85 MB
g++	path_graph_root_centroid_02	AC	125 ms	85 MB
g++	random_00	AC	188 ms	36 MB
g++	random_01	AC	215 ms	42 MB
g++	random_02	AC	64 ms	8 MB
g++	random_03	AC	102 ms	39 MB
g++	random_04	AC	83 ms	26 MB