tree/test/Lowest_Common_Ancestor.test.cpp

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• Lowest Common Ancestor (tree/lca.hpp)

Code

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

#include <bits/stdc++.h>

using namespace std;

#include "tree/lca.hpp"

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; ++i) {
    int p;
    cin >> p;
    g[p].push_back(i), g[i].push_back(p);
  }
  auto lca_tree = lca(g, 0);
  while (q--) {
    int u, v;
    cin >> u >> v;
    cout << lca_tree.get(u, v) << '\n';
  }
}

#line 1 "tree/test/Lowest_Common_Ancestor.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#include <bits/stdc++.h>

using namespace std;

#line 2 "tree/lca.hpp"

struct lca {
  int n, l;
  vector<int> in, out, depth;
  vector<vector<int>> up;
  lca(const vector<vector<int>> &g, int root)
      : n(g.size()),
        l(__lg(n) + 1),
        in(n),
        out(n),
        depth(n),
        up(n, vector<int>(l)) {
    int timer = 0;
    auto dfs = [&](auto dfs, int p, int u, int d = 0) -> void {
      in[u] = timer++;
      up[u][0] = p;
      depth[u] = d;
      for (int i = 1; i < l; ++i) {
        up[u][i] = up[up[u][i - 1]][i - 1];
      }
      for (auto v : g[u])
        if (v != p) dfs(dfs, u, v, d + 1);
      out[u] = timer++;
    };
    dfs(dfs, root, root);
  };
  bool is_anc(int u, int v) const { return in[u] <= in[v] && out[u] >= out[v]; }
  int dist(int u, int v) const {
    return depth[u] + depth[v] - 2 * depth[get(u, v)];
  }
  int get(int u, int v) const {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int i = l - 1; i >= 0; --i) {
      if (!is_anc(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
  }
};
#line 8 "tree/test/Lowest_Common_Ancestor.test.cpp"

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; ++i) {
    int p;
    cin >> p;
    g[p].push_back(i), g[i].push_back(p);
  }
  auto lca_tree = lca(g, 0);
  while (q--) {
    int u, v;
    cin >> u >> v;
    cout << lca_tree.get(u, v) << '\n';
  }
}

Back to top page