Company Queries II

#include <iostream>
#include <vector>

using namespace std;

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

    int n, q;
    cin >> n >> q;
    vector<int> bosses(n - 1);
    for (int i = 0; i < n - 1; i++)
        cin >> bosses[i];

    int maxk = 0;
    while ((1 << maxk) <= n)
        maxk++;
    vector<vector<int>> pre(n, vector<int>(maxk, 0));
    maxk--;

    int k = 0;
    while (k <= maxk) {
        for (int i = 2; i < n + 1; i++) {
            if (k == 0) {
                pre[i - 1][k] = bosses[i - 2];
            } else {
                int prev = pre[i - 1][k - 1];
                pre[i - 1][k] = prev == 0 ? 0 : pre[prev - 1][k - 1];
            }
        }
        k++;
    }

    vector<int> depth(n + 1, 0);
    for (int i = 2; i < n + 1; i++)
        depth[i] = depth[bosses[i - 2]] + 1;

    int a, b;
    for (int dc = 0; dc < q; dc++) {
        cin >> a >> b;

        if (depth[a] < depth[b]) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        int diff = depth[a] - depth[b];

        int j = 0;
        while (diff > 0) {
            if (diff % 2 != 0)
                a = pre[a - 1][j];

            diff /= 2;
            j++;
        }

        if (a != b) {
            for (int k1 = maxk; k1 >= 0; k1--) {
                if (pre[a - 1][k1] != pre[b - 1][k1]) {
                    a = pre[a - 1][k1];
                    b = pre[b - 1][k1];
                }
            }
            a = pre[a - 1][0];
        }
        cout << a << "\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