Company Queries II

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int MAXN = 200005;
const int MAXK = 18;  // Because log2(2e5) ≈ 17.6

int n, q;
vector<int> adj[MAXN];
int up[MAXN][MAXK];  // up[node][k] = 2^k-th ancestor of node
int depth[MAXN];

void dfs(int u, int parent) {
    up[u][0] = parent;
    for (int k = 1; k < MAXK; ++k) {
        if (up[u][k - 1] != 0)
            up[u][k] = up[up[u][k - 1]][k - 1];
        else
            up[u][k] = 0;
    }
    for (int v : adj[u]) {
        if (v != parent) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b])
        swap(a, b);

    // Lift node a up so that depth[a] == depth[b]
    int diff = depth[a] - depth[b];
    for (int k = 0; k < MAXK; ++k) {
        if ((diff >> k) & 1)
            a = up[a][k];
    }

    if (a == b)
        return a;

    // Lift both a and b up until their ancestors are the same
    for (int k = MAXK - 1; k >= 0; --k) {
        if (up[a][k] != 0 && up[a][k] != up[b][k]) {
            a = up[a][k];
            b = up[b][k];
        }
    }

    return up[a][0];  // or up[b][0]
}

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

    cin >> n >> q;
    // Since employee 1 is the root, we set its parent to 0
    for (int v = 2; v <= n; ++v) {
        int u;
        cin >> u;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    depth[1] = 0;
    dfs(1, 0);

    while (q--) {
        int a, b;
        cin >> a >> b;
        int ans = lca(a, b);
        cout << ans << '\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