Company Queries II

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

using namespace std;

const int MAXN = 200005;
const int LOG = 20; // Suficiente para cubrir hasta 2^19 = 524288
vector<int> adj[MAXN];
int up[MAXN][LOG]; // Ancestros a potencias de dos
int depth[MAXN]; // Profundidad de cada nodo

void dfs(int v, int p) {
    up[v][0] = p; // Padre inmediato de v
    for (int i = 1; i < LOG; ++i) {
        if (up[v][i-1] != -1)
            up[v][i] = up[up[v][i-1]][i-1];
        else
            up[v][i] = -1; // No existe este ancestro
    }
    
    for (auto u : adj[v]) {
        if (u != p) {
            depth[u] = depth[v] + 1;
            dfs(u, v);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b])
        swap(a, b);
    
    // Igualar la profundidad de a y b
    for (int i = LOG - 1; i >= 0; --i) {
        if (depth[a] - (1 << i) >= depth[b])
            a = up[a][i];
    }
    
    if (a == b)
        return a;
    
    // Ascender en el árbol hasta encontrar el ancestro común más bajo
    for (int i = LOG - 1; i >= 0; --i) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    
    return up[a][0]; // El padre de a (o b) es el LCA
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    // Leer la jerarquía de empleados
    for (int i = 2; i <= n; ++i) {
        int boss;
        cin >> boss;
        adj[boss].push_back(i);
    }
    
    // Preparar la tabla de ancestros y profundidades
    depth[1] = 0; // La profundidad del director general es 0
    dfs(1, -1); // Comenzar DFS desde el director general
    
    // Resolver cada consulta
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << 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