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);
0123456lo que te dan: n − 1 aristassin raíz no hay padres ni hijos: solo vecinosenraizar(0, -1)0prof 01prof 12prof 13prof 24prof 25prof 26prof 3colgado de la raíz 0padre[4] = 1, padre[1] = 0, padre[0] = −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
    }
}
0tam 71tam 42tam 23tam 14tam 25tam 16tam 17º4º6º1º3º5º2ºtam[1] = 1 + tam[3] + tam[4]= 1 + 1 + 2 = 4el padre suma DESPUÉS de quecada hijo terminó su dfs:los nodos 3 y 6 terminan antesque el nodo 1 (4º) y la raíz 0 (7º)el orden de término (post-orden) es el orden natural de toda DP en árboles

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 upadre[u]Actualización
64tam[4]: 1 + 1 = 2
52tam[2]: 1 + 1 = 2
41tam[1]: 1 + 2 = 3
31tam[1]: 3 + 1 = 4
20tam[0]: 1 + 2 = 3
10tam[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";
0d 21d 12d 33d 04d 25d 46d 31º: desde 3, el más lejano es 5(da lo mismo desde dónde partir)0d 21d 32d 13d 44d 45d 06d 52º: desde 5, el más lejano es 6diámetro = 5 aristas: 5-2-0-1-4-6

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).

0prof 01prof 123prof 2456prof 3lca(3, 6) = 1dist = prof[3] + prof[6] − 2 · prof[1] = 2 + 3 − 2 = 3prof[3] cuenta el tramo 0→1→3,prof[6] el tramo 0→1→4→6:el tramo 0→1 se contó dos vecesy no está en el caminobinary lifting: up[0][6] = 4,up[1][6] = 1 (dos saltos = 2¹)el camino 3→1→4→6 tiene 3 aristas, y pasa por el ancestro común

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^k

Para 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.

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?

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í.

#ProblemaDificultadQué practica
1Subordinates (CSES 1674)★★★ (—)tamaños de subárbol, tal cual
2Tree 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?

Rwuvprofundidad 0profundidad 2profundidad 5profundidad 4Cada segmento une dos nodos: cuesta una arista.

Si el diagrama no cabe, deslízalo horizontalmente.


← 20 - Fenwick y segment tree · Ruta de Aprendizaje · 22 - Programación dinámica II →