Company Queries II

#include <bits/stdc++.h>
using namespace std;
// clang-format off
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#ifdef DO_DBG
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template <typename T> using v = vector<T>;
template <typename T> using us = unordered_set<T>;
template <typename K, typename V> using um = unordered_map<K, V>;
template <typename K, typename V> using p = pair<K, V>;
template <typename T> using pq = priority_queue<T>;
template <typename T> using nl = numeric_limits<T>;
constexpr int MOD = 1e9 + 7;
constexpr int INF = 1e9;
constexpr ld EPS = 1e-9;
// fancy 
#define loopi(n) for (auto i : std::views::iota(0, n))
#define loopj(n) for (int j = 0; j < n; j++)
#define loopk(n) for (int k = 0; k < n; k++)
#define loopz(n) for (int z = 0; z < n; z++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sq(x) ((x) * (x))
template <typename... Args> void read(Args&... args) { ((cin >> args), ...); }
#define d(...) int __VA_ARGS__; read(__VA_ARGS__);
#define dv(x, n) vector<int> x(n); for (int i = 0; i < n; i++) cin >> x[i];
#define dvl(x, n) vector<long long> x(n); for (int i = 0; i < n; i++) cin >> x[i];
#define dvd(x, n) vector<double> x(n); for (int i = 0; i < n; i++) cin >> x[i];
template <typename T> struct Mat {
  int n, m;
  std::vector<T> a;
  Mat(int n, int m, T val = T()) : n(n), m(m), a(n * m, val) {}
  T &operator()(int i, int j) { return a[i * m + j]; }
  const T &operator()(int i, int j) const { return a[i * m + j]; }
};
// clang-format on

template <class F> struct y_combinator {
  F f;
  template <class... Args> decltype(auto) operator()(Args &&...args) const {
    return f(*this, std::forward<Args>(args)...);
  }
};

int main() {
  fastio;
  d(n, q);

  int rows = 1;
  for (int k = 1; k * 2 <= n; k *= 2)
    rows++;

  Mat<int> anc(rows, n);
  v<us<int>> adj(n);

  // fill the first layer
  // and create adj
  anc(0, 0) = -1;
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    p--;

    anc(0, i) = p;
    adj[p].insert(i);
  }

  v<int> depth(n);

  // we need to run dfs to calculate depths.
  y_combinator([&](auto dfs, int v) -> void {
    // while were here on the node, we can precompute the ancestors
    // - we don't need dfs for it but we do dfs anyway since we need depths
    // EDIT: REMEMBER TO DO IT BEFORE RECURSION
    for (int i = 1; i < rows; i++) {
      auto mid = anc(i - 1, v);
      anc(i, v) = mid == -1 ? -1 : anc(i - 1, mid);
    }

    for (auto c : adj[v]) {
      depth[c] = depth[v] + 1;
      dfs(c);
    }
  })(0);

  while (q--) {
    d(a, b);
    a--, b--;
    dbg(a, b, depth[a], depth[b]);

    // a is deeper, lift a
    if (depth[a] < depth[b])
      swap(a, b);

    int k = depth[a] - depth[b];
    dbg(k);
    dbg(anc.a);
    while (k) {
      int row = 0, p = 1;
      while (p * 2 <= k) {
        row++;
        p *= 2;
      }
      dbg(a, p, row);
      a = anc(row, a);
      k -= p;
      dbg(a, k);
    }

    // if b is an ancestor of a
    if (a == b)
      cout << b + 1 << "\n";
    else {
      // we want lift a and b together as far us possible such that they still
      // have different ancestors
      for (int i = rows - 1; i >= 0; i--) {
        dbg(i);
        if (anc(i, a) != anc(i, b)) {
          a = anc(i, a);
          b = anc(i, b);
        }
      }
      cout << anc(0, a) + 1 << "\n";
    }
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED