Company Queries II

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>

typedef long long ll;

using namespace std;


const int MAXN = 200005;
const int LOG = 20;             // 2^20 > 1e6

int root = 1;
vector<int> g[MAXN];
int up[MAXN][LOG];
int depth[MAXN];

void dfs(int u, int p) {
    up[u][0] = p;
    for (int j = 1; j < LOG; ++j)
        up[u][j] = (up[u][j-1] != -1) ? up[ up[u][j-1] ][j-1] : -1;

    for (int v : g[u]) if (v != p) {
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

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

    int diff = depth[a] - depth[b];
    for (int j = 0; j < LOG; ++j)
        if (diff & (1 << j))
            a = up[a][j];

    if (a == b) return a;

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

    return up[a][0];
}


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

    // freopen("input.txt", "r", stdin); // TODO: REMOVE THIS YOU STUPID ****

    int n, q;
    cin >> n >> q;
    for (int i = 2; i <= n; ++i) {
        int a;
        cin >> a;
        g[a].push_back(i);
        g[i].push_back(a);
    }

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

    while (q--) {
        int u, k;
        cin >> u >> k;
        cout << LCA(u, k) << "\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