Company Queries II

#include <iostream>
#include <vector>
#include <algorithm>



int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n, q;
    std::cin >> n >> q;
    std::vector<int> level(n+1);
    int max = 18;
    std::vector<std::vector<int>> bosses(n+1, std::vector<int>(max));
    for (int i = 0; i < max; i++) bosses[1][i] = 1;
    for (int i = 2; i <= n; i++) {
        int tmp;
        std::cin >> tmp;
        level[i] = level[tmp] + 1;
        bosses[i][0] = tmp;
        for (int j = 1; j < max; j++) bosses[i][j] = bosses[bosses[i][j - 1]][j - 1];
    }
    while (q--) {
        int a, b;
        std::cin >> a >> b;
        if (level[a] < level[b]) {
            std::swap(a, b);
        }
        int diff = level[a] - level[b];
        for (int i = 0; i < max; i++) if (diff & (1 << i)) a = bosses[a][i];
        if (a == b) {
            std::cout << a << '\n';
            continue;
        }
        for (int k = max - 1; k >= 0; k--) {
            if (bosses[a][k] != bosses[b][k]) {
                    a = bosses[a][k];
                    b = bosses[b][k];
            }
        }
        std::cout << bosses[a][0] << '\n';
    }
}

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