Company Queries II

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


int main(int argc, char **argv) {
    int n, q;
    std::cin >> n >> q;

    int LIMIT = 18;
    std::vector<std::vector<int>> up(n+1, std::vector<int>(LIMIT, 1));
    std::vector<int> depth(n+1, 0);

    for (int i=2; i<=n; i++) {
        std::cin >> up[i][0];
        depth[i] = depth[up[i][0]] + 1;
        for (int j=1; j<LIMIT; j++) {
            up[i][j] = up[up[i][j-1]][j-1];
        }
    }

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

        if (depth[a] < depth[b]) {
            std::swap(a, b);
        }

        for (int j=LIMIT-1; j>=0; j--) {
            if (depth[up[a][j]] >= depth[b]) {
                a = up[a][j];
            }
        }

        if (a != b) {
            for (int j=LIMIT-1; j>=0; j--) {
                if (up[a][j] != up[b][j]) {
                    a = up[a][j];
                    b = up[b][j];
                }
            }
            a = up[a][0];
        }

        std::cout << a << 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