DP en árboles (rerooting)
Tema: Árboles · temarios: Syllabus OCI · Syllabus IOI
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué hace
Calcula, para CADA nodo como raíz, una agregación sobre todo el árbol en O(n) total: una pasada hacia arriba y otra propagando hacia abajo.
Complejidad: O(n).
Cuándo usarlo
Cuando necesitas la respuesta vista desde todos los nodos (no solo la raíz): suma de distancias, conteos, etc.
Implementación recomendada (C++)
// Ejemplo: suma de distancias de cada nodo al resto, en O(n).
struct Reroot {
int n; vector<vector<int>> g;
vector<long long> sub, ans; vector<int> cnt;
Reroot(int n) : n(n), g(n), sub(n,0), ans(n,0), cnt(n,0) {}
void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); }
void dfs1(int u, int p) { // tamaños y suma de distancias en el subárbol
cnt[u] = 1;
for (int v : g[u]) if (v != p) { dfs1(v, u); cnt[u] += cnt[v]; sub[u] += sub[v] + cnt[v]; }
}
void dfs2(int u, int p) { // reenraíza de u a cada hijo v
for (int v : g[u]) if (v != p) { ans[v] = ans[u] - cnt[v] + (n - cnt[v]); dfs2(v, u); }
}
void run(int root = 0) { dfs1(root, -1); ans[root] = sub[root]; dfs2(root, -1); }
};⚠️ Notas
La transición de reenraizado (de u a v) es el corazón: cambia según la agregación. Aquí: al mover la raíz al hijo v, cnt[v] nodos se acercan 1 y los n-cnt[v] restantes se alejan 1. ⚠️ Este ejemplo es amable porque la suma se puede restar; en el caso general (máximos, por ejemplo) no se puede quitar un hijo restando: se guardan prefijos y sufijos de la agregación de los hijos para obtener ‘todos menos v’ en O(1). ⚠️ La recursión aquí es de profundidad O(n) (un árbol en forma de camino la lleva al máximo). En la IOI eso no es problema: el run_cpp.sh oficial sube la pila al mismo valor que la memoria (2 GB en 2023). En tu propia máquina sí lo es: el límite por defecto son 8 MB y revienta cerca de n = 120.000. Si se cae localmente pero pasa en el juez, es esto — corre ulimit -s unlimited (o ulimit -s 65520 en macOS) antes de probar.