Company Queries II

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 18;
vector<int> V[1<<N];
int D[1<<N];
int T[N][1<<N];

int fp(int i, int s) {
  for (int j = 0; j < N; ++j) {
    if (s&(1<<j)) {
      i = T[j][i];
    }
  }
  return i;
}

int fca(int a, int b) {
  if (D[a] < D[b]) swap(a,b);
  a = fp(a, D[a] - D[b]);
  if (a == b) return a;
  for (int i = N-1; i >= 0; --i) {
    if (T[i][a] != T[i][b]) {
      a = T[i][a];
      b = T[i][b];
    }
  }
  return T[0][a];
}

void dfs(int i, int p, int d) {
  D[i] = d;
  T[0][i] = p;
  for (int j : V[i]) {
    if (j != p) dfs(j,i,d+1);
  }
}

int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    int a;
    cin >> a;
    V[a-1].push_back(i);
    V[i].push_back(a-1);
  }
  dfs(0,0,0);
  for (int i = 1; i < N; ++i) {
    for (int j = 0; j < n; ++j) {
      T[i][j] = T[i-1][T[i-1][j]];
    }
  }
  for (int i = 0; i < q; ++i) {
    int a, b;
    cin >> a >> b;
    cout << fca(a-1, b-1) + 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