Linear Memory Binary Liftings LCA

#include <bits/stdc++.h>

using namespace std;

struct LinearBinups {
    vector<int> depth;
    vector<int> parent;
    vector<int> jump;

    LinearBinups(int n, int root = 0) {
        depth.resize(n);
        parent.resize(n);
        jump.resize(n);
        parent[root] = jump[root] = root;
    }

    void add_leaf(int v, int par) {
        parent[v] = par;
        depth[v] = depth[par] + 1;
        if (depth[par] - depth[jump[par]] == depth[jump[par]] - depth[jump[jump[par]]]) {
            jump[v] = jump[jump[par]];
        } else {
            jump[v] = par;
        }
    }

    int find_la(int v, int k) {
        int h = max(depth[v] - k, 0);
        while (depth[v] != h) {
            if (depth[jump[v]] >= h) {
                v = jump[v];
            } else {
                v = parent[v];
            }
        }
        return v;
    }

    int find_lca(int v, int u) {
        if (depth[v] > depth[u]) {
            v = find_la(v, depth[v] - depth[u]);
        } else {
            u = find_la(u, depth[u] - depth[v]);
        }
        while (v != u) {
            if (jump[v] != jump[u]) {
                v = jump[v];
                u = jump[u];
            } else {
                v = parent[v];
                u = parent[u];
            }
        }
        return v;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    LinearBinups linear_binups(n);

    for (int i = 1; i < n; i++) {
        int par;
        cin >> par; // par < i
        linear_binups.add_leaf(i, par - 1);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int v, u;
        cin >> v >> u;
        cout << linear_binups.find_lca(v - 1, u - 1) + 1 << '\n';
    }
}