🧱 LCA con binary lifting
Estructura de datos · Se implementa a mano · Tema: Árboles Catálogo completo: Catálogo de estructuras
📍 Dónde se aprende: módulo 21 de la Ruta de Aprendizaje.
Qué hace
En un árbol con raíz elegida, devuelve el ancestro compartido de mayor profundidad. Cada nodo cuenta como ancestro de sí mismo. Precalcula saltos de 2^k aristas para responder muchas consultas sin subir una arista a la vez.
Operaciones y costo
| Operación | Costo | Notas |
|---|---|---|
| Precálculo | O(n log n) | un DFS + la tabla de saltos |
| LCA(u, v) | O(log n) | |
| Distancia entre dos nodos | O(log n) | prof[u] + prof[v] − 2·prof[lca] |
| Espacio | O(n log n) |
Por dentro
Primero iguala las profundidades: si un nodo está 5 niveles más abajo, sube 4 y luego 1. Si coinciden, ese nodo es el LCA. Si no, prueba saltos de mayor a menor: solo mueve ambos cuando sus destinos son distintos, para permanecer debajo del ancestro compartido. Al terminar son hijos de ese ancestro y devuelve su padre.
Ejemplo. Con raíz 0 y aristas 0–1, 0–2, 1–3, 1–4, 2–5, LCA(3,4)=1, LCA(3,5)=0 y LCA(1,4)=1. Las profundidades son {0,1,1,2,2,2}. Para 3 y 5, sus padres 1 y 2 difieren: ambos suben una vez; ahora comparten padre 0. La distancia entre 3 y 5 es 2+2−2·0=4 aristas.
La tabla up[k][v] guarda el ancestro a 2^k pasos: up[k][v] = up[k−1][up[k−1][v]] compone dos saltos iguales. En este ejemplo, desde 3 un paso llega a 1 y dos pasos llegan a 0.
Cuándo usarla
Consultas de LCA, distancia entre nodos en árbol, saltar k ancestros. Base de muchos problemas sobre árboles.
Implementación recomendada (C++)
struct LCA {
int LOG; vector<int> depth; vector<vector<int>> up;
LCA(const vector<vector<int>>& g, int root = 0) {
int n = g.size();
LOG = 1; while ((1 << LOG) < n) LOG++;
depth.assign(n, 0); up.assign(LOG, vector<int>(n, root));
vector<int> par(n, root); vector<char> vis(n, 0);
stack<int> st; st.push(root); vis[root] = 1; // DFS iterativo
while (!st.empty()) {
int u = st.top(); st.pop();
for (int v : g[u]) if (!vis[v]) {
vis[v] = 1; par[v] = u; depth[v] = depth[u] + 1; st.push(v);
}
}
for (int v = 0; v < n; v++) up[0][v] = par[v];
for (int k = 1; k < LOG; k++)
for (int v = 0; v < n; v++) up[k][v] = up[k-1][up[k-1][v]];
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
int d = depth[a] - depth[b];
for (int k = 0; k < LOG; k++) if (d >> k & 1) a = up[k][a];
if (a == b) return a;
for (int k = LOG - 1; k >= 0; k--)
if (up[k][a] != up[k][b]) { a = up[k][a]; b = up[k][b]; }
return up[0][a];
}
int dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
};⚠️ Notas
Contrato de esta implementación. Recibe un árbol no vacío, conectado y sin ciclos, con vértices 0..n−1; root y las consultas deben ser índices válidos. Para un árbol no dirigido, cada arista aparece en las listas de ambos extremos. La distancia cuenta aristas, no pesos. Elegir otra raíz puede cambiar el LCA, pero no esa distancia. La función pública implementa lca y dist; los saltos de ancestros se usan internamente, no se ofrece aquí una función pública para k-ésimo ancestro.
Cómo leer d >> k & 1: pregunta si el bit k de d está encendido, o sea ¿tengo que dar el salto de 2^k? — subir d niveles es dar los saltos de los bits encendidos de d, igual que armar el número d sumando potencias de 2. La raíz es su propio ancestro (up[k][root] = root). Para árboles grandes, evita la recursión profunda (de ahí el DFS iterativo).