Company Queries II

#include <bits/stdc++.h>

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

    int n, q;
    std::cin >> n >> q;

    std::vector<std::vector<int>> children(n + 1);
    for (int i = 2; i <= n; i++) {
        int boss;
        std::cin >> boss;
        children[boss].emplace_back(i);
    }

    std::vector<int> depth(n + 1);
    std::vector<int> first(n + 1);
    std::vector<int> order;

    std::stack<std::pair<int, int>> stack;
    stack.emplace(1, 0);

    depth[1] = 1;
    first[1] = 0;
    order.emplace_back(1);

    while (!stack.empty()) {
        const int node = stack.top().first;
        int &nextChild = stack.top().second;

        if (nextChild < static_cast<int>(children[node].size())) {
            const int child = children[node][nextChild++];
            depth[child] = depth[node] + 1;

            first[child] = static_cast<int>(order.size());
            order.emplace_back(child);
            stack.emplace(child, 0);
        } else {
            stack.pop();

            if (!stack.empty()) {
                order.emplace_back(stack.top().first);
            }
        }
    }

    const int m = static_cast<int>(order.size());

    std::vector log2(m + 1, 0);
    for (int i = 2; i <= m; i++) {
        log2[i] = log2[i / 2] + 1;
    }

    const int powers = log2[m] + 1;
    std::vector table(powers, std::vector<int>(m));

    for (int a = 0; a < m; a++) {
        table[0][a] = a;
    }

    for (int k = 1; k < powers; k++) {
        const int length = 1 << k;

        for (int a = 0; a + length <= m; a++) {
            const int b = a + length - 1;
            const int w = (b - a + 1) / 2;

            const int leftMin = table[k - 1][a];
            const int rightMin = table[k - 1][a + w];
            table[k][a] = (depth[order[leftMin]] < depth[order[rightMin]]) ? leftMin : rightMin;
        }
    }

    while (q--) {
        int a, b;
        std::cin >> a >> b;

        int left = first[a];
        int right = first[b];
        if (left > right) {
            std::swap(left, right);
        }

        const int k = log2[right - left + 1];

        const int leftMin = table[k][left];
        const int rightMin = table[k][right - (1 << k) + 1];

        if (depth[order[leftMin]] <= depth[order[rightMin]]) {
            std::cout << order[leftMin] << std::endl;
        } else {
            std::cout << order[rightMin] << std::endl;
        }
    }

    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