Binary lifting template

binaryLifing.cpp

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

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class BinaryLifting {
    ll MAXLOG;
    vector<vector<ll>> parent;
    vector<ll> depth;

    void dfs(vector<vector<ll>>& graph, ll u, ll p) {
        parent[u][0] = p;
        depth[u] = depth[p] + 1;

        for (ll i : graph[u]) {
            if (i == p) {
                continue;
            }

            dfs(graph, i, u);
        }
    }

   public:
    BinaryLifting(vector<vector<ll>>& graph, ll root = 1, ll maxLog = 18) {
        MAXLOG = maxLog;
        parent = vector<vector<ll>>(graph.size(), vector<ll>(MAXLOG + 1));
        depth = vector<ll>(parent.size());

        dfs(graph, root, 0);

        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(ll x, ll k) {
        for (ll i = 0; i <= MAXLOG; i++) {
            if (k & (1 << i)) {
                x = parent[x][i];
            }
        }

        return x;
    }

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

        b = jump(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() {
    ll n, q;
    cin >> n >> q;

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

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

        graph[x].push_back(i);
    }
    
    BinaryLifting BL(graph);

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

        cout << BL.lca(a, b) << '\n';
    }
}