Enunciado y contexto
Este problema difícil de codificación evalúa la descomposición de árboles, el preprocesamiento de distancias y las consultas dinámicas. El árbol tiene n vértices y n-1 aristas; las operaciones llegan online, el estado inicial tiene un vértice negro y las alternancias son arbitrarias. Una consulta debe devolver la distancia actual al negro más cercano sin volver a recorrer todo el árbol.
Qué evalúa el entrevistador
- Comenzar con una solución base correcta e identificar el recorrido repetido como el cuello de botella.
- Demostrar que cada nodo tiene una cadena de ancestros de centroide de longitud logarítmica y mantener sus distancias.
- Manejar la exclusión de componentes, distancias duplicadas, un conjunto negro inicialmente vacío y límites de enteros.
- Comparar la descomposición de centroides con BFS multifuente, descomposición heavy-light y variantes solo de inserción.
Preguntas aclaratorias para hacer
Confirma que el árbol sea estático, si las aristas tienen peso unitario o positivo, si las operaciones son online, si la consulta también necesita el identificador del nodo y si se permite el reordenamiento. Los pesos positivos en las aristas siguen funcionando al almacenar distancias ponderadas; las actualizaciones de aristas requieren un diseño de árbol dinámico diferente.
Estructura de respuesta de 30 segundos
Primero daría la solución base: BFS desde u es lineal por consulta. Luego construiría una descomposición de centroides. Cada nodo almacena su distancia a cada ancestro de centroide, y cada centroide almacena la distancia mínima desde un nodo actualmente negro. Una consulta minimiza "distancia desde u al centroide más la mejor distancia a un negro de ese centroide" a lo largo de los ancestros de centroide de u; una alternancia actualiza la misma cadena. La cadena es logarítmica, por lo que las operaciones son logarítmicas aparte de los costos del heap, con un preprocesamiento lineal-logarítmico.
Respuesta detallada paso a paso
1. Establecer la solución base y el cuello de botella
BFS desde u es correcto, pero una consulta puede visitar casi todos los vértices. Después de alternancias repetidas no hay un resumen reutilizable de qué vértices negros están cerca de u. Un BFS global multifuente solo ayuda cuando el conjunto negro cambia en lotes, no con alternancias online.
2. Elegir centroides y construir cadenas de ancestros
Encuentra un centroide de la componente conexa actual de modo que al eliminarlo cada componente tenga como máximo la mitad del tamaño original. Aplica recursión sobre esas componentes para formar un árbol de centroides. Un vértice original u tiene una cadena de ancestros de centroide; preprocesa un par (centroid, distance) para cada enlace. El tamaño de la componente se reduce a la mitad en cada nivel, por lo que la longitud de la cadena es logarítmica.
3. Mantener los invariantes de actualización y consulta
Para cada centroide c, mantén el mínimo dist(v,c) sobre todos los vértices v actualmente negros. Un min-heap con eliminación perezosa (lazy deletion) o un multiset permite esto. update(u) inserta o elimina dist(u,c) a lo largo de la cadena de centroides de u. query(u) minimiza dist(u,c) + best[c] en esa cadena. Cualquier camino desde u hasta un v negro pasa por su centroide compartido en algún nivel de descomposición, por lo que un candidato representa el camino óptimo; no se omite ninguna rama.
4. Manejar distancias duplicadas y eliminación en el heap
Con dos heaps, inserta en el heap activo y registra las eliminaciones en el heap inactivo; antes de leer la cima, elimina los pares iguales. Las distancias iguales requieren almacenar tanto la distancia como el id del nodo; de lo contrario, eliminar un nodo puede eliminar otro. Aplica una actualización para el nodo negro inicial y devuelve un centinela documentado como -1 cuando el conjunto esté vacío.
5. Complejidad y alternativas
El preprocesamiento recorre cada nivel de descomposición, lo que toma O(n log n) de tiempo y O(n log n) enlaces almacenados. Cada operación escanea una cadena logarítmica y realiza operaciones de heap, agregando un factor logarítmico por el heap. Si los nodos solo se insertan, un solo heap es más simple; si la operación es un agregado asociativo sobre caminos, la descomposición heavy-light con un segment tree es más directa; las operaciones offline pueden usar divide y vencerás temporal.
6. Esqueleto de implementación en C++
El código siguiente utiliza aristas unitarias, alterna nodos negros y responde consultas de distancia más cercana. El código de producción puede reemplazar los recorridos recursivos con pilas explícitas para árboles muy profundos; la forma recursiva mantiene visible el invariante.
#include <bits/stdc++.h>
using namespace std;
struct Entry { int d, u; bool operator>(const Entry& o) const { return tie(d,u) > tie(o.d,o.u); } };
int n; vector<vector<int>> g; vector<int> sub, dead, black;
vector<vector<pair<int,int>>> chain;
vector<priority_queue<Entry, vector<Entry>, greater<Entry>>> liveHeap, deadHeap;
void calcSize(int u,int p){sub[u]=1;for(int v:g[u])if(v!=p&&!dead[v]){calcSize(v,u);sub[u]+=sub[v];}}
int findCentroid(int u,int p,int total){for(int v:g[u])if(v!=p&&!dead[v]&&sub[v]>total/2)return findCentroid(v,u,total);return u;}
void collect(int u,int p,int c,int d){chain[u].push_back({c,d});for(int v:g[u])if(v!=p&&!dead[v])collect(v,u,c,d+1);}
void decompose(int entry){calcSize(entry,-1);int c=findCentroid(entry,-1,sub[entry]);dead[c]=1;collect(c,-1,c,0);for(int v:g[c])if(!dead[v])decompose(v);}
void clean(int c){while(!liveHeap[c].empty()&&!deadHeap[c].empty()&&liveHeap[c].top().d==deadHeap[c].top().d&&liveHeap[c].top().u==deadHeap[c].top().u){liveHeap[c].pop();deadHeap[c].pop();}}
void update(int u){black[u]^=1;for(auto [c,d]:chain[u]){if(black[u])liveHeap[c].push({d,u});else deadHeap[c].push({d,u});}}
int query(int u){const int INF=1e9;int ans=INF;for(auto [c,d]:chain[u]){clean(c);if(!liveHeap[c].empty())ans=min(ans,d+liveHeap[c].top().d);}return ans==INF?-1:ans;}Respuesta modelo de alta calidad
Transformaría el árbol estático en un árbol de centroides. Durante el preprocesamiento, cada vértice registra su distancia a cada ancestro de centroide; cada centroide almacena la distancia mínima desde un vértice negro actual. Una alternancia inserta o elimina de forma perezosa la distancia a lo largo de esa cadena de ancestros. Una consulta minimiza la distancia a cada centroide más la mejor distancia a un negro de ese centroide. Cada camino se encuentra con su centroide compartido en algún nivel, por lo que el vértice negro óptimo está representado. La cadena de centroides es logarítmica, lo que da un preprocesamiento de O(n log n) y operaciones de cadena logarítmica, multiplicadas por los costos del heap. Con solo inserciones eliminaría el heap de eliminación; con aristas cambiantes elegiría una estructura de árbol dinámico.
Errores comunes
- BFS para cada consulta → correcto pero demasiado lento online → enunciar la solución base y luego usar la cadena de centroides.
- Actualizar solo el centroide más cercano → un camino puede cruzar un centroide superior → almacenar cada ancestro de centroide.
- Eliminación perezosa solo por distancia → nodos con distancias iguales colisionan → incluir el id del nodo en la clave del heap.
- Tratar la descomposición de centroides como LCA → resuelven tareas diferentes → indicar que esto mantiene la distancia desde un nodo a un conjunto dinámico.
- Ignorar un conjunto negro vacío → devuelve un valor grande no inicializado → definir y explicar un centinela
-1.
Preguntas de seguimiento y respuestas
¿Cómo cambian el algoritmo los pesos positivos en las aristas?
Acumula los pesos de las aristas mientras recolectas cada cadena de centroides y almacena las distancias ponderadas en los heaps. La descomposición sigue utilizando el conteo de vértices por componente; el invariante de distancia mínima no cambia para pesos no negativos.
¿Qué pasa si la consulta debe devolver el id del nodo negro más cercano?
Almacena (distance, nodeId) y compara lexicográficamente. Esto proporciona un id determinista cuando hay empates de distancia; la consulta lleva tanto la mejor distancia como el id.
¿Por qué no mantener solo el centroide padre de u?
El nodo negro más cercano puede estar en una componente hija diferente, con el camino encontrándose con u en un centroide superior. Verificar solo un padre omite óptimos entre componentes, por lo que se requiere la cadena completa de ancestros.
¿Cuándo es mejor la descomposición heavy-light?
Úsala para agregados asociativos sobre caminos, consultas arbitrarias de caminos entre dos vértices o una operación sobre el conjunto negro que no sea "distancia mínima desde un vértice a un conjunto dinámico". La descomposición de centroides es más fuerte cuando cada consulta está anclada en un vértice y agrega sobre un conjunto cambiante.