21 · Árboles I
Estructuras y algoritmos avanzados · Ruta de Aprendizaje
Antes de empezar. DFS y BFS: 15 - Grafos I - BFS y DFS y 16 - Distancias en grafos. Para los saltos binarios, operadores de bits de 20 - Fenwick y segment tree.
🎯 Objetivos
Al terminar este módulo sabes:
- Explotar la propiedad que define a un árbol: n−1 aristas, camino único.
- Calcular tamaños de subárbol con un DFS (la base de toda DP en árboles).
- Enraizar un árbol con el patrón
dfs(u, p)y calcular profundidades. - Encontrar el diámetro, y usar el LCA para medir distancias.
📖 La lección
Qué tiene de especial un árbol
Un árbol es un grafo conexo con n−1 aristas: sin ciclos y con un único camino entre cada par de nodos. Esa unicidad lo cambia todo: no hay “camino más corto” que buscar (hay uno solo), y colgarlo de una raíz ordena el mundo en padres, hijos y subárboles. El panorama completo del tema, en Árboles.
Antes de recorrer, fijemos el vocabulario. Con raíz 0 y aristas 0–1, 0–2, 1–3 y 1–4, el padre de 3 es 1 y sus ancestros son 3, 1 y 0 (incluimos al propio nodo). Los hijos de 1 son 3 y 4. Su subárbol incluye al 1 y a todos sus descendientes: {1,3,4}. La profundidad cuenta aristas desde la raíz: 0 tiene profundidad 0, 1 tiene 1 y 3 tiene 2. Elegir otra raíz cambia estas relaciones, pero no las conexiones.
Primero: enraizar el árbol
Cuando el enunciado entrega n−1 aristas sin dirección, tú eliges una raíz y cuelga todo de ahí. Enraizar es literalmente un DFS que, al bajar, se acuerda de por dónde vino:
En los ejemplos de esta clase los nodos son 0..n-1 y n >= 1.
Antes de llamar, reserva padre.assign(n, -1) y prof.assign(n, 0);
con raíz 0, llama enraizar(0, -1). La lista ady debe tener n posiciones
y contener cada arista en ambas direcciones. En árboles muy profundos,
una versión iterativa evita agotar la pila de llamadas.
// supone: vector<vector<int>> ady; // la lista de adyacencia del módulo 15
vector<int> padre, prof;
void enraizar(int u, int p) {
padre[u] = p;
for (int v : ady[u])
if (v != p) { // el único vecino prohibido es de donde vengo
prof[v] = prof[u] + 1;
enraizar(v, u);
}
}
// llamada inicial: prof[raiz] = 0; enraizar(raiz, -1);Si el diagrama no cabe, deslízalo horizontalmente.
Ese if (v != p) es el sello de todo el módulo. En un grafo cualquiera
necesitas visitado[]; en un árbol no hay ciclos, así que basta con no
devolverse por la arista por la que entraste. Verás el patrón dfs(u, p) en
cada problema de árboles que resuelvas de aquí en adelante.
El patrón fundamental: DFS que acumula
Casi todo cálculo sobre árboles es ese mismo DFS, pero donde cada nodo absorbe los resultados de sus hijos antes de responderle a su padre. El ejemplo canónico — tamaño de cada subárbol:
// usa: ady
vector<int> tam; // global; tam.assign(n, 0) antes de llamar
void dfs(int u, int p) {
tam[u] = 1; // se cuenta a sí mismo
for (int v : ady[u]) if (v != p) {
dfs(v, u);
tam[u] += tam[v]; // absorbe los subárboles de sus hijos
}
}Si el diagrama no cabe, deslízalo horizontalmente.
Fíjate en el orden: el tam[u] += va después del dfs(v, u), porque
necesita que el hijo ya haya terminado. Cambia el “absorbe” y tienes sumas,
máximos, alturas, conteos de hojas… Este patrón es la semilla de la DP en
árboles (DP en árboles (rerooting) cuando llegue el momento de la
versión avanzada).
La misma acumulación sin recursión
Podemos guardar un orden donde cada padre aparezca antes que sus hijos; al recorrerlo al revés, cada hijo ya tiene su tamaño. Este bloque reemplaza las llamadas a enraizar y dfs y usa las mismas variables:
// usa: ady, padre, prof, tam
int cantidad = ady.size(); // árbol no vacío, nodos 0..cantidad-1
padre.assign(cantidad, -1);
prof.assign(cantidad, 0);
tam.assign(cantidad, 1);
vector<int> orden = {0};
for (int i = 0; i < (int)orden.size(); i++) {
int u = orden[i];
for (int v : ady[u]) if (v != padre[u]) {
padre[v] = u;
prof[v] = prof[u] + 1;
orden.push_back(v);
}
}
for (int i = cantidad - 1; i > 0; i--) {
int u = orden[i];
tam[padre[u]] += tam[u];
}En el árbol de la figura anterior, un orden posible es
[0,1,2,3,4,5,6]: cada padre aparece antes que sus hijos. Al recorrerlo al
revés, cada subárbol está completo cuando lo sumamos a su padre:
Procesamos u | padre[u] | Actualización |
|---|---|---|
| 6 | 4 | tam[4]: 1 + 1 = 2 |
| 5 | 2 | tam[2]: 1 + 1 = 2 |
| 4 | 1 | tam[1]: 1 + 2 = 3 |
| 3 | 1 | tam[1]: 3 + 1 = 4 |
| 2 | 0 | tam[0]: 1 + 2 = 3 |
| 1 | 0 | tam[0]: 3 + 4 = 7 |
No sumamos la raíz a ningún padre: por eso el segundo ciclo se detiene
antes del índice 0 de orden. Hacer las sumas en el orden original enviaría
hacia arriba tamaños todavía incompletos; por ejemplo, 1 enviaría 1 antes
de recibir los aportes de 3 y 4.
Cuesta O(n) tiempo y memoria, también en un árbol con forma de camino. El bloque supone que la entrada es un árbol; no sustituye el marcado de visitados en un grafo general.
El diámetro: el camino más largo
El truco de los dos recorridos: parte de cualquier nodo, anda al más
lejano a; desde a, anda al más lejano b. La distancia a→b es el
diámetro. Con el BFS del módulo 15 son cuatro
líneas:
// supone: int n; vector<vector<int>> ady; // nodos 0..n-1
// devuelve {nodo más lejano desde s, su distancia}
pair<int,int> mas_lejano(int s) {
vector<int> d(n, -1); queue<int> q;
d[s] = 0; q.push(s);
int lejano = s;
while (!q.empty()) {
int u = q.front(); q.pop();
if (d[u] > d[lejano]) lejano = u;
for (int v : ady[u]) if (d[v] == -1) { d[v] = d[u] + 1; q.push(v); }
}
return {lejano, d[lejano]};
}
// dentro de main, después de leer el árbol:
// cout << mas_lejano(mas_lejano(0).first).second << "\n";Si el diagrama no cabe, deslízalo horizontalmente.
La propiedad que usamos. En un árbol sin pesos, cualquier vértice más lejano de un origen es extremo de algún diámetro; el segundo recorrido mide su longitud. La intuición es que, como los caminos son únicos, alejarse no puede producir atajos alternativos. Esto orienta el algoritmo, pero no es por sí solo una demostración: la ficha Diámetro de un árbol desarrolla la justificación y la variante por alturas.
LCA: el ancestro común más bajo
Queremos la distancia entre 3 y 4 en el pequeño árbol anterior. Sus ancestros comunes son 1 y 0. El más bajo es el de mayor profundidad, aquí el 1: es donde se encuentran primero al subir hacia la raíz. Se llama LCA. El camino 3→1→4 tiene dos aristas; ambos suben un nivel hasta ese encuentro.
En general, desde u hasta ese ancestro hay prof[u] − prof[lca(u,v)]
aristas, y desde v hay prof[v] − prof[lca(u,v)]. Sumarlas da:
dist(u, v) = prof[u] + prof[v] − 2·prof[lca(u, v)]
(los dos suben hasta el ancestro; la parte compartida se contó dos veces y por eso se resta dos veces).
Si el diagrama no cabe, deslízalo horizontalmente.
Encontrar el LCA a lo bruto es fácil: iguala profundidades subiendo el más hondo, y después sube los dos de a un paso hasta que se junten. Eso es O(profundidad) por consulta — perfecto para entender la idea, demasiado lento para 2·10⁵ consultas sobre un árbol en forma de camino.Esta versión directa usa los padres y profundidades ya calculados:
// usa: padre, prof
int lca_simple(int u, int v) {
while (prof[u] > prof[v]) u = padre[u];
while (prof[v] > prof[u]) v = padre[v];
while (u != v) { u = padre[u]; v = padre[v]; }
return u;
}Con aristas 0–1, 0–2, 1–3, 1–4 y raíz 0, los nodos 3 y 4
están a profundidad 2. Ambos suben al 1, así que su LCA es 1 y su distancia
es 2 + 2 - 2·1 = 2. No se sube desde la raíz: los nodos se encuentran
antes. La distancia y el diámetro aquí cuentan aristas sin pesos.
Ampliación: saltos binarios
Binary lifting es esa misma subida, pero de a saltos de potencias de 2.
La tabla up[k][v] = “el ancestro de v a 2ᵏ pasos” se llena con una identidad
preciosa: saltar 2ᵏ es saltar 2ᵏ⁻¹ dos veces.
// supone: int n, LOG; vector<vector<int>> up; // up.assign(LOG, vector<int>(n)); LOG = 18 basta para n ≤ 2·10⁵
// up[0][v] = padre[v] (y la raíz es su propio padre)
for (int k = 1; k < LOG; k++)
for (int v = 0; v < n; v++)
up[k][v] = up[k-1][ up[k-1][v] ]; // dos saltos de 2^(k-1) = uno de 2^kPara conectar ambas representaciones, asigna up[0][v] = padre[v] para
los nodos distintos de la raíz y up[0][raiz] = raiz. Así los saltos
que llegan a la raíz se quedan allí; nunca se usa −1 como índice.
Por ejemplo, subir 5 niveles equivale a subir 4 y luego 1: usa up[2][v] y después up[0][v]. Para hallar un LCA, primero igualas las profundidades; luego pruebas saltos de mayor a menor y solo subes ambos si sus ancestros son diferentes. Así permanecen debajo del ancestro común; al terminar, su padre es el LCA. Si un salto los lleva al mismo ancestro, saltarlo podría pasarse del LCA y se prueba uno menor.
Con esa tabla, subir d niveles es mirar los bits de d (módulo 20): por cada bit encendido, das ese salto. Precálculo O(n log n), consulta O(log n). La implementación completa —con la segunda mitad, la que baja a los dos nodos en paralelo sin pasarse— está en LCA con binary lifting, y es la que necesitas para el problema ⭐.
🏋️ Práctica
Práctica directa: Leer un árbol enraizado
Usa aristas 0–1,0–2,1–3,1–4,2–5,4–6 y raíz 0. Imprime tamaños de subárbol para 0..6: 7 4 2 1 2 1 1. La distancia de 3 a 6 es 3.
Idea para comprobar tu solución
Calcula los hijos antes de sumarlos al padre. El LCA de 3 y 6 es 1; sus profundidades 2 y 3 dan 2+3−2·1=3.
Variación: Cambiar la raíz
El árbol tiene aristas 0–1, 1–2 y 1–3. ¿Cuál es el LCA de 2 y 3 con raíz 0? ¿Y con raíz 2? ¿Cambia la distancia entre ellos?
Una pista, si la necesitas
Un nodo también es ancestro de sí mismo.
Contrastar el razonamiento
Con raíz 0, el LCA es 1; con raíz 2, es 2. La distancia sigue siendo dos aristas. La relación de ancestro depende de la raíz; el camino del árbol no cambia.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Los ejemplos recursivos de enraizar y acumular pueden agotar la pila en árboles profundos. El bloque iterativo anterior y el BFS del diámetro evitan esa profundidad; el LCA simple también usa ciclos. El límite de pila depende del entorno y de cada llamada, no de un número fijo de nodos.
En este módulo la práctica es toda del CSES: la OCI casi no toca árboles — son material de campamento e IOI, no de las fases regional y nacional— así que no hay enunciados chilenos equivalentes que ofrecerte aquí.
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Subordinates (CSES 1674) | ★★★ (—) | tamaños de subárbol, tal cual |
| 2 | Tree Diameter (CSES 1131) | ★★★ (—) | dos recorridos; aquí se usa BFS |
| 3 | ⭐ Company Queries II (CSES 1688) | ★★★★ (—) | LCA con binary lifting |
Para pensar: por qué el ancestro se resta dos veces
Un árbol está enraizado en R. Los vértices u y v tienen profundidades 5 y 4, y su ancestro común más bajo w tiene profundidad 2. Todas las aristas miden 1. ¿Cuántas aristas tiene el camino entre u y v?
Si el diagrama no cabe, deslízalo horizontalmente.
Ver razonamiento
De u a w hay
5 − 2 = 3aristas; de w a v hay4 − 2 = 2. La distancia es 5. Sumar las profundidades de u y v daría 9 porque incluiría dos veces el tramo de R a w, que no pertenece al camino buscado. De ahí saleprof[u] + prof[v] − 2·prof[LCA(u,v)]. Si u es ancestro de v, el LCA es u y la misma fórmula se reduce aprof[v] − prof[u].
← 20 - Fenwick y segment tree · Ruta de Aprendizaje · 22 - Programación dinámica II →