Company Queries II

#include <iostream>
#include <queue>
#include <utility>
#include <vector>


const int MAX_DEPTH = 18; // ceil(log(n=2*10^5)) ~ 18


int lca(int a, int b, std::vector<std::vector<int>>& up, std::vector<int>& depth){
  if (depth[a] < depth[b]) std::swap(a, b);

  int diff = depth[a] - depth[b];
  for (int j = 0; j < MAX_DEPTH; ++j)
    if (diff & (1 << j)) a = up[a][j]; //move "a" up by exactly "diff" levels.

  if (a == b) return a;

  // Get largest possible ancestor, if the ancestors isn't equal, we haven't converged yet, and it is safe to lift both a and b to that ancestor. 
  // When they reach that, the effective depth left to reach the root is reduced exactly by j levels, so we don't need to check the previous levels again. 
  // In the case, the furthest ancestors are equal, we continue the loop in case of a lower common ancestor.
  for (int j = MAX_DEPTH-1; j >= 0; --j)
    if (up[a][j] != up[b][j]) { 
      a = up[a][j];
      b = up[b][j];
    }
  return up[a][0];
}




int main() {
  int n, q;
  std::cin >> n >> q;

  std::vector<std::vector<int>> up(n+1, std::vector<int>(MAX_DEPTH));
  std::vector<int> depth(n+1);

  // for bfs to get depth
  std::vector<std::vector<int>> adj(n+1); 

  for (int i = 2; i <= n; ++i) {
    int boss;
    std::cin >> boss;
    adj[boss].push_back(i);
    adj[i].push_back(boss);
    up[i][0] = boss;
  }

  // initialize root
  up[1][0] = 1;
  depth[1] = 0;
  std::queue<int> queue;
  queue.push(1);

  while (!queue.empty()) {
    int v = queue.front(); queue.pop();
    for (int u : adj[v]) {
      if (u != up[v][0]) {
        depth[u] = depth[v] + 1;
        queue.push(u);
      }
    }
  }

  // binary lifting table
  for (int j = 1; j < MAX_DEPTH; ++j)
    for (int v = 1; v <= n; ++v)
      up[v][j] = up[ up[v][j-1] ][j-1];

  std::vector<std::pair<int, int>> queries(q);
  for(int i = 0; i<q; ++i){
    std::cin >> queries[i].first >> queries[i].second;
  }
  for(int i = 0; i<q; ++i){
    std::cout << lca(queries[i].first, queries[i].second, up, depth) << '\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