Company Queries II

#include <iostream>
#include <vector>

using namespace std;

const int LOG = 18;   // 2^18 = 262144 > 2*10^5

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

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

  vector<vector<int>> up(LOG, vector<int>(n + 1));
  vector<int> depth(n + 1, 0);

  up[0][1] = 1;
  for(int i = 2; i <= n; ++i){
    cin >> up[0][i];
    depth[i] = depth[up[0][i]] + 1; 
  }

  for(int j = 1; j < LOG; ++j){
    for(int v = 1; v <= n; ++v){
      up[j][v] = up[j-1][ up[j-1][v] ];
    }
  }

  while(q--){
    int a, b;
    cin >> a >> b;

    if(depth[a] < depth[b]) swap(a, b);
    int d = depth[a] - depth[b];
    for(int j = 0; j < LOG; ++j){
      if(d & (1 << j)) a = up[j][a];
    }

    if(a == b){
      cout << a << endl;
      continue;
    }

    for(int j = LOG - 1; j >= 0; --j){
      if(up[j][a] != up[j][b]){
        a = up[j][a];
        b = up[j][b];
      }
    }

    cout << up[0][a] << endl;
  }
}

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