Árboles
LCA, DP en árboles, descomposición, problemas sobre árboles.
Volver a los 11 temas · Referencia · temarios: Syllabus OCI · Syllabus IOI.
📍 Clases relacionadas: módulos 21 de la Ruta de Aprendizaje.
📋 En el temario OCI: no figura; es material posterior a la fase nacional.
Un árbol es un grafo conexo sin ciclos: entre cada par de nodos hay exactamente un camino. Esa unicidad es la que habilita técnicas que en un grafo cualquiera no existirían.
📌 Qué abarca
- Definiciones: hoja, diámetro, bosque; árbol con raíz (padre, hijo, ancestro, subárbol).
- Árbol de expansión; centro y centroide.
- LCA en O(log n) con binary lifting (o Euler tour + RMQ con sparse table).
- DP en árboles y rerooting.
- Heavy-Light Decomposition (consultas sobre caminos con segment tree).
- Centroid decomposition.
⛔ Fuera del syllabus IOI
- Estructuras para árboles dinámicos / link-cut trees (modificar la topología en línea).
🎯 En competencia
En la OCI — Un árbol puede aparecer en la Nacional como grafo conexo sin ciclos que se recorre con DFS, pero LCA, DP en árboles o HLD no se piden en ninguna fase. Es el primer tema que se abre camino al campamento. Ninguno de los 97 problemas OCI del vault es de este tema.
En la IOI — Los árboles aparecen muchísimo. Diámetro, DP sobre subárboles y LCA son básicos; HLD y centroid son para las subtareas altas. Ver también Programación Dinámica.
⚠️ La trampa típica
La recursión profunda: un árbol de 10⁵ nodos «en línea» (un camino) hace que el DFS recursivo apile 10⁵ llamadas. Y al calcular hacia arriba, cuidado con procesar un nodo antes que sus hijos.
🧱 Estructuras de datos
Se implementan a mano — hay que saber construirlas:
Todas juntas y comparables en el Catálogo de estructuras.
⚙️ Algoritmos y técnicas
🌍 Problemas IOI
De más abordable a más duro, según el puntaje promedio que sacaron los competidores: una media alta sugiere más puntos parciales accesibles, no más soluciones completas. Consulta también el porcentaje de 100 y los prerrequisitos.
| Problema | Año | Media (puntos parciales) | Lograron 100 |
|---|---|---|---|
| Stations | 2020 | 51/100 | 26% |
| Migrations | 2025 | 38/100 | 0% |
| Nowruz | 2017 | 34/100 | 0% |
| Ball Machine | 2026 | 30/100 | 1% |
| Split the Attractions | 2019 | 27/100 | 2% |
| Digital Circuit | 2022 | 25/100 | 15% |
| Closing Time | 2023 | 23/100 | 3% |
| Tree | 2024 | 18/100 | 1% |
| Beech Tree | 2023 | 15/100 | <1% |
| Towns | 2015 | 14/100 | 2% |