Lowest common ancestor with binary jumping (binary lifting)

LCABinaryJumping.cpp

// https://cses.fi/problemset/task/1688/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll MAXLOG = 18;

void preCalc(vector<vector<ll>>& parent) {
    for(ll k = 1; k <= MAXLOG; k++) {
        for(ll x = 1; x < parent.size(); x++) {
            parent[x][k] = parent[parent[x][k - 1]][k - 1];
        }
    }
}

ll jump(vector<vector<ll>>& parent, ll x, ll k) {
    for(ll i = 0; i <= MAXLOG; i++) {
        if(k & (1 << i)) {
            x = parent[x][i];
        }
    }

    return x;
}

void calcDepth(vector<vector<ll>>& graph, vector<ll>& depth, ll u) {
    for(ll i : graph[u]) {
        depth[i] = depth[u] + 1;
        
        calcDepth(graph, depth, i);
    }
}

ll lca(vector<vector<ll>>& parent, vector<ll>& depth, ll a, ll b) {
    if(depth[a] > depth[b]) {
        swap(a, b);
    }

    b = jump(parent, b, depth[b] - depth[a]);

    if(a == b) {
        return a;
    }

    for(ll i = MAXLOG; i >= 0; i--) {
        if(parent[a][i] != parent[b][i]) {
            a = parent[a][i], b = parent[b][i];
        }
    }

    return parent[a][0];
}

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    
    ll n, q;
    cin >> n >> q;

    vector<vector<ll>> graph(n + 1), parent(n + 1, vector<ll>(MAXLOG + 1));
    vector<ll> depth(n + 1);

    for(ll i = 2; i <= n; i++) {
        ll x;
        cin >> x;

        graph[x].push_back(i);
        parent[i][0] = x;
    }

    preCalc(parent);
    calcDepth(graph, depth, 1);

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

        cout << lca(parent, depth, a, b) << '\n';
    }
}