Company Queries II

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

using namespace std;

const int max_log = 18;
int n, q;
vector<vector<int>> ancestors;
vector<int> depths;
vector<vector<int>> GRAPH;

void dfs(int node, int parent) {
    ancestors[node][0] = parent;
    for (int i = 1; i < max_log; i++) {
        if (ancestors[node][i-1] != 0) {
            ancestors[node][i] = ancestors[ancestors[node][i-1]][i-1];
        }
    }
    for (int adj : GRAPH[node]) {
        if (adj != parent) {
            depths[adj] = depths[node] + 1;
            dfs(adj, node);
        }
    }
}

int res(int a, int b) {
    if (depths[a] < depths[b]) {
        swap(a, b);
    }

    int diff = depths[a] - depths[b];
    for (int i = 0; i < max_log; i++) {
        if ((diff >> i) & 1) {
            a = ancestors[a][i];
        }
    }

    if (a == b) {
        return a;
    }

    for (int i = max_log - 1; i >= 0; i--) {
        if (ancestors[a][i] != ancestors[b][i]) {
            a = ancestors[a][i];
            b = ancestors[b][i];
        }
    }
    return ancestors[a][0];
}

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

    cin >> n >> q;
    ancestors.assign(n + 1, vector<int>(max_log, 0));
    depths.assign(n + 1, 0);
    GRAPH.assign(n + 1, vector<int>());

    for (int i = 2; i <= n; i++) {
        int x; cin >> x;
        GRAPH[i].push_back(x);
        GRAPH[x].push_back(i);
    }

    dfs(1, 0);

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;
        cout << res(a, b) << "\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