test/graph/lca.test.cpp

• View this file on GitHub
• Last update: 2025-10-20 17:37:23+08:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• src/graph/lca.hpp
• src/misc/read.hpp

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/lca.hpp"
#include "../../src/misc/read.hpp"

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

#line 1 "test/graph/lca.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/graph/lca.hpp"
// 时间复杂度: 预处理 $\mathcal{O}(n \log n)$; 查询 $\mathcal{O}(1)$
struct LCA {
  int n, m, cur_dfn = 0;
  vector<int> dfn, dep;
  vector<vector<int>> G, st;
  LCA(int n)
      : n(n), m(32 - __builtin_clz(n)), dfn(n, -1), dep(n), G(n),
        st(m, vector<int>(n)) {}
  void adde(int u, int v) { G[u].PUSHB(v), G[v].PUSHB(u); }
  void work(int root) {
    dfs(root, root);
    for (int j = 1; j < m; j++)
      for (int i = 0; i + (1 << j) <= n; i++)
        st[j][i] = op4st(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
  }
  int query(int u, int v) const {
    if (u == v) return u;
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
    int q = __lg(v - u);
    return op4st(st[q][u + 1], st[q][v + 1 - (1 << q)]);
  }

 private:
  int op4st(int u, int v) const { return dfn[u] < dfn[v] ? u : v; }
  void dfs(int u, int fa_) {
    st[0][dfn[u] = cur_dfn++] = fa_;
    for (int v : G[u])
      if (v != fa_) dep[v] = dep[u] + 1, dfs(v, u);
  }
};
#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/lca.test.cpp"

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

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	154 ms	81 MB
g++	almost_line_01	AC	157 ms	80 MB
g++	binary_00	AC	191 ms	72 MB
g++	binary_01	AC	181 ms	72 MB
g++	binary_02	AC	188 ms	72 MB
g++	example_00	AC	5 ms	4 MB
g++	line_00	AC	124 ms	70 MB
g++	line_01	AC	138 ms	83 MB
g++	line_02	AC	52 ms	12 MB
g++	line_03	AC	81 ms	77 MB
g++	line_04	AC	63 ms	51 MB
g++	max_line_00	AC	155 ms	89 MB
g++	max_line_01	AC	158 ms	89 MB
g++	max_line_02	AC	153 ms	89 MB
g++	max_random_00	AC	205 ms	72 MB
g++	max_random_01	AC	211 ms	72 MB
g++	max_random_02	AC	189 ms	72 MB
g++	path_graph_root_centroid_00	AC	133 ms	80 MB
g++	path_graph_root_centroid_01	AC	133 ms	80 MB
g++	path_graph_root_centroid_02	AC	131 ms	80 MB
g++	random_00	AC	135 ms	57 MB
g++	random_01	AC	160 ms	67 MB
g++	random_02	AC	52 ms	10 MB
g++	random_03	AC	110 ms	63 MB
g++	random_04	AC	72 ms	42 MB

Back to top page