CompProg

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Zeldacrafter/CompProg

:heavy_check_mark: tests/yosupo/binary_lifting.lca.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#include "../../code/graphs/LCABL.cc"

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, q;
    cin >> n >> q;

    vvi adj(n);
    F0R(i, n - 1) {
        int u;
        cin >> u;
        adj[i + 1].pb(u);
        adj[u].pb(i + 1);
    }
    
    LCA lca(adj);
    while(q--) {
        int u, v;
        cin >> u >> v;
        cout << lca.query(u, v) << endl;
    }
}
#line 1 "tests/yosupo/binary_lifting.lca.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/graphs/LCABL.cc"
struct LCA {
  int n, logN, root;
  vvi up;
  vi h;
  LCA(vvi& adj, int r = 0)
      : n{SZ(adj)}, logN{31 - __builtin_clz(n)},
        root{r}, up(n, vi(logN + 1, root)),
        h(n, -1) { 
    build(adj);
  }
  void build(vvi& adj) {
    queue<int> q;
    q.push(root);
    h[root] = 0;
    while (SZ(q)) {
      int v = q.front();
      q.pop();
      for (int u : adj[v])
        if (h[u] == -1) {
          h[u] = h[v] + 1;
          q.push(u);
          up[u][0] = v;
        }
    }
    FOR (exp, 1, logN + 1)
      F0R (v, n)
        if (up[v][exp - 1] != -1)
          up[v][exp] = up[up[v][exp - 1]][exp - 1];
  }
  int jumpUp(int v, int amt) {
    for (int i = 0; v != -1 && (1 << i) <= amt; ++i)
      if (amt & (1 << i)) 
        v = up[v][i];
    return v;
  }
  int query(int v, int u) {
    v = jumpUp(v, max(0, h[v] - h[u]));
    u = jumpUp(u, max(0, h[u] - h[v]));
    if (u == v) return u;
    for (int l = logN; ~l; --l) {
      int jmpU = up[u][l], jmpV = up[v][l];
      if (jmpU == -1 || jmpV == -1) continue;
      if (jmpU != jmpV) {
        u = jmpU;
        v = jmpV;
      }
    }
    return up[v][0];
  }
};
#line 4 "tests/yosupo/binary_lifting.lca.test.cpp"

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, q;
    cin >> n >> q;

    vvi adj(n);
    F0R(i, n - 1) {
        int u;
        cin >> u;
        adj[i + 1].pb(u);
        adj[u].pb(i + 1);
    }
    
    LCA lca(adj);
    while(q--) {
        int u, v;
        cin >> u >> v;
        cout << lca.query(u, v) << endl;
    }
}
Back to top page