Lowest Common Ancestor (LCA) es el ancestro común más profundo de dos nodos en un árbol (o DAG). Es una query fundamental en árboles con aplicaciones en distances, queries de árbol, y problemas de grafos.

Binary Lifting

Preprocesa up[u][k] = el ancestro de u a distancia 2^k.

up[u][0] = parent[u]
up[u][k] = up[ up[u][k-1] ][k-1]

Complejidad: O(n log n) preprocessing, O(log n) query.

Query Binary Lifting

lca(u, v):

1. Asegura depth[u] <= depth[v].
2. Sube v hasta misma profundidad que u usando binary lifting.
3. Si u == v: retorna u.
4. Desde k = log n down to 0: si up[u][k] != up[v][k], sube ambos.
5. Retorna parent[u] (o up[u][0]).

Ejemplo

Árbol:

    1
   / \\
  2   3
 / \\
4   5

lca(4, 5):

• depth[4]=2, depth[5]=2 (iguales).
• k=1: up[4][1]=1, up[5][1]=1 → iguales, no suben.
• k=0: up[4][0]=2, up[5][0]=2 → iguales, no suben.
• Retorna parent[4]=2.

Resultado: 2.

Euler Tour + RMQ

1. Haz DFS y guarda el orden de visita (Euler tour).
2. Para cada nodo, guarda su depth en un array paralelo.
3. LCA(u,v) = nodo con mínimo depth en el rango entre primera aparición de u y primera aparición de v.
4. Usa Sparse Table para RMQ en O(1).

Comparación

Aplicaciones

• Tree queries — distancia entre nodos, k-th ancestor
• LCA en grafos — lowest common ancestors en DAGs
• Bioinformática — árboles filogenéticos
• Enseñanza — introduce binary lifting y RMQ

Trayectoria de Práctica

1. Implementa binary lifting; traza lca(4,5) en el ejemplo.
2. Implementa Euler tour + Sparse Table.
3. Compara tiempos de query entre métodos.
4. Investiga Tarjan’s offline LCA: ¿cómo responde todas las queries en O(n+Q)?
5. Investiga LCA en árboles dinámicos (Link-Cut Tree).