Company Queries II

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;

ll n, maxLog;
vector<vector<ll>> up;
vector<ll> depth;

void preprocess(vector<ll>& parent) {
    depth[1] = 0;
    for (ll i = 2; i <= n; i++) {
        depth[i] = depth[parent[i]] + 1;
    }
    
    for (ll i = 1; i <= n; i++) {
        up[i][0] = parent[i];
    }
    
    for (ll k = 1; k < maxLog; k++) {
        for (ll node = 1; node <= n; node++) {
            up[node][k] = up[up[node][k-1]][k-1];
        }
    }
}

ll ancestor(ll x, ll k) {
    for (ll i = 0; i < maxLog; i++) {
        if (k & (1 << i)) {
            x = up[x][i];
            if (x == 0) return 0;
        }
    }
    return x;
}

ll lca(ll a, ll b) {
    if (depth[a] < depth[b]) swap(a, b);
    
    a = ancestor(a, depth[a] - depth[b]);
    
    if (a == b) return a;
    
    for (ll k = maxLog - 1; k >= 0; k--) {
        if (up[a][k] != up[b][k]) {
            a = up[a][k];
            b = up[b][k];
        }
    }
    
    return up[a][0];
}

int main() {
    ll q;
    cin >> n >> q;
    maxLog = ceil(log2(n)) + 1;
    up.assign(n + 1, vector<ll>(maxLog, 0));
    depth.assign(n + 1, 0);
    vector<ll> parent(n + 1, 0);

    for(ll i = 2; i <= n; i++){
       cin >> parent[i];
    }

    preprocess(parent);
    
    for(ll i = 0; i < q; i++){
        ll a, b;
        cin >> a >> b;
        cout << lca(a, b) << "\n";
    }

    return 0;
}

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