Binary Jumping (binary lifting)

binaryJumping.cpp

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

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

    return x ?: -1;
}

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

int main() {
    ll n, q;
    cin >> n >> q;

    vector<vector<ll>> parent(n + 1, vector<ll>(19));

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

    preCalc(parent);

    while (q--) {
        ll x, k;
        cin >> x >> k;

        cout << jump(parent, x, k) << '\n';
    }
}