Company Queries II

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000;
const int LOG = 20; // log2(4e5) ≈ 19

int n, q;
vector<int> children[MAXN + 1];
int depth[MAXN + 1];
vector<int> euler;
int first[MAXN + 1];
int st[LOG + 1][2 * MAXN];
int logval[2 * MAXN + 1];

// DFS pour Euler tour
void dfs(int u, int d) {
    depth[u] = d;
    first[u] = (int)euler.size();
    euler.push_back(u);
    for (int v : children[u]) {
        dfs(v, d + 1);
        euler.push_back(u);
    }
}

// Construit la Sparse Table pour RMQ sur les profondeurs
void buildSparseTable() {
    int m = euler.size();
    for (int i = 0; i < m; ++i)
        st[0][i] = euler[i];

    for (int i = 2; i <= m; ++i)
        logval[i] = logval[i / 2] + 1;

    for (int k = 1; (1 << k) <= m; ++k) {
        for (int i = 0; i + (1 << k) <= m; ++i) {
            int a = st[k - 1][i];
            int b = st[k - 1][i + (1 << (k - 1))];
            st[k][i] = (depth[a] < depth[b]) ? a : b;
        }
    }
}

// Renvoie le LCA de a et b
int lca(int a, int b) {
    int i = first[a], j = first[b];
    if (i > j) swap(i, j);
    int len = j - i + 1;
    int k = logval[len];
    int x = st[k][i];
    int y = st[k][j - (1 << k) + 1];
    return (depth[x] < depth[y]) ? x : y;
}

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

    cin >> n >> q;
    vector<int> boss(n + 1);

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

    dfs(1, 0);
    buildSparseTable();

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