Entrevista de código: ¿Cómo mantendrías un bosque dinámico con un link-cut tree?

Pregunta y alcance

Tienes un bosque dinámico cuyas aristas se pueden agregar o eliminar y cuyos vértices contienen números enteros. Admite link(u,v), cut(u,v), consultas de máximo en camino y sumas en camino. Explica la representación, access, makeroot, etiquetas perezosas (lazy tags), corrección y complejidad.

La estructura de árboles dinámicos de Sleator y Tarjan une dos árboles y corta una arista con operaciones amortizadas O(log n). La señal esperada en la entrevista es separar los caminos del árbol representado de los caminos preferidos almacenados en árboles splay auxiliares, en lugar de recitar una plantilla.

Lo que el entrevistador está evaluando

• Saber que un link-cut tree mantiene un bosque representado y árboles splay auxiliares para los caminos preferidos.
• Implementar isRoot, push, pull, rotaciones y splay correctamente.
• Explicar cómo access convierte el camino hacia la raíz representada en un camino preferido.
• Usar una etiqueta de reversión perezosa para caminos no enraizados sin corromper el orden de propagación.
• Validar la conectividad antes de link y la arista exacta antes de cut.
• Indicar el tiempo amortizado O(log n) y discutir arreglos, profundidad de recursión y pruebas aleatorias.

Preguntas para aclarar primero

1. ¿Se garantiza que la estructura siga siendo un bosque o las operaciones pueden crear ciclos? Los link-cut trees no resuelven la conectividad general en grafos dinámicos.
2. ¿La actualización de caminos es suma, asignación o tanto máximo como mínimo? Cada una requiere un álgebra diferente de agregados y etiquetas perezosas.
3. ¿Los valores están en los vértices o en las aristas? Representa una arista como un vértice virtual cuando se necesiten valores en las aristas.
4. ¿Se requiere persistencia o concurrencia, o es una estructura online de un solo hilo?
5. ¿La entrada puede contener enlaces duplicados, cortes inexistentes o bucles hacia el mismo nodo?

Una respuesta de 30 segundos

Uso un splay auxiliar por cada vértice representado. ch almacena los hijos del splay y fa es o bien un padre auxiliar o un padre en el camino representado. access sube por el árbol reemplazando cada hijo derecho con el camino ya procesado; makeroot accede y revierte perezosamente el árbol auxiliar. link verifica la conectividad, hace makeroot en un extremo y lo conecta. cut hace makeroot en un extremo, accede al otro, verifica que el subárbol izquierdo sea exactamente el extremo de la arista y lo desconecta. Se hace push antes de las rotaciones y pull después de las actualizaciones; las operaciones son O(log n) amortizadas.

Análisis paso a paso

1. Representar dos relaciones de árboles

Los hijos del splay auxiliar describen el orden en un camino preferido. Cuando un nodo es una raíz auxiliar, fa no es un padre de splay; es el padre del camino en el árbol representado. Por lo tanto, isRoot(x) debe comprobar que x no sea ninguno de los hijos de fa[x], no simplemente si fa[x] es cero.

2. Mantener agregados y etiquetas perezosas

Para el máximo en camino, pull(x) combina el valor en x con ambos subárboles auxiliares. Una suma en camino utiliza una etiqueta add; la reversión de camino intercambia los hijos bajo una etiqueta rev. push debe propagar la reversión antes de la suma, o de lo contrario definir un orden de composición comprobado.

pull(x): mx[x] = max(value[x], mx[ch[x][0]], mx[ch[x][1]])
applyAdd(x,d): value[x] += d; mx[x] += d; add[x] += d
applyRev(x): swap(ch[x][0], ch[x][1]); rev[x] ^= true

3. Implementar access

Establece last = 0 y recorre desde x a través de fa: aplica splay a y, establece el hijo derecho de y como last, haz pull a y, luego establece last como y y continúa. Finalmente, aplica splay al x original. El camino desde x hasta la raíz representada es ahora un único camino preferido cuyo orden en el splay puede responder a consultas de agregados de caminos.

4. Implementar makeroot

makeroot(x) llama a access(x) y aplica rev a x. x se convierte en la raíz del árbol representado, por lo que link(x,y) puede unir dos árboles en la dirección prevista. No reviertas recursivamente el árbol representado; el splay auxiliar puede llevar la reversión perezosa.

5. Implementar link y cut

link(x,y) llama a makeroot(x), rechaza findroot(y) == x y luego establece fa[x] = y. Para cut(x,y), llama a makeroot(x) y a access(y). Si la arista existe, el hijo izquierdo de y es x y x no tiene hijo derecho; desconecta ese hijo y limpia su padre. Esta comprobación estructural evita cortar una arista diferente del camino.

6. Consultar y actualizar un camino

split(x,y) es makeroot(x); access(y), dejando el splay auxiliar de y como el camino de x a y. Lee mx[y] para obtener el máximo o aplica applyAdd a y para una actualización de camino. No es necesario restaurar los caminos preferidos; el siguiente access los reorganizará.

7. Complejidad y pruebas

El análisis de Sleator–Tarjan otorga un costo amortizado de O(log n) para link, cut, root y evert, con un espacio de O(n). Comprueba de forma cruzada una implementación pequeña frente a un bosque de adyacencia ingenuo: genera links y cuts válidos, compara máximos y sumas en caminos, e incluye árboles de un solo nodo, makeroot repetidos, accesos consecutivos, cortes inválidos, valores iguales y negativos.

Respuesta de ejemplo de alta calidad

Haría que fa represente tanto a un padre auxiliar como a un padre de camino representado y los distinguiría con isRoot, en lugar de tratar al árbol representado como un árbol binario ordinario. Cada nodo del splay almacena su valor, el máximo del subárbol, una etiqueta de reversión y una etiqueta de suma. access expone un camino preferido; makeroot lo revierte perezosamente; split(x,y) hace que el splay de y represente el camino de x a y.

link aplica makeroot y rechaza extremos ya conectados. cut aplica makeroot y access, y luego verifica que el subárbol izquierdo de y sea exactamente x antes de desconectarlo. Haz push a los ancestros antes de las rotaciones y pull después de los cambios. La estructura utiliza un tiempo amortizado de O(log n) y un espacio de O(n); las comprobaciones cruzadas aleatorias contra un bosque ingenuo cubren agregados, operaciones inválidas y combinaciones de etiquetas perezosas.

Errores comunes

• Evaluar fa[x] == 0 para una raíz auxiliar → un padre de camino puede ser distinto de cero → usa la comprobación basada en hijos isRoot.
• Omitir los pushes de ancestros antes de rotar → la reversión o suma permanece oculta → recolecta los ancestros y aplica push en orden inverso.
• Cortar sin comprobar la arista → se elimina la arista de camino incorrecta → verifica la forma del subárbol izquierdo después de makeroot/access.
• Enlazar sin una comprobación de conectividad → un ciclo rompe el invariante de bosque → compara las raíces primero.
• Tratar al splay posterior al access como todo el árbol representado → solo queda expuesto un camino preferido → confía en futuras operaciones de access.
• Probar consultas pero no actualizaciones → los errores de etiquetas perezosas quedan ocultos → compara sumas en caminos aleatorias con un bosque ingenuo.

Preguntas y respuestas de seguimiento

¿Cómo mantendrías el mínimo o el XOR en un camino?

Reemplaza pull con el agregado de monoide requerido. El XOR no es sensible al orden bajo reversión; un agregado no conmutativo debe definir la dirección del camino y el orden de reversión explícitamente.

¿Cómo incluyes pesos en las aristas?

Divide cada arista en un vértice virtual cuyo valor sea el peso de la arista y luego utiliza la agregación de vértices habitual. Administra ese vértice virtual al hacer link y cut.

¿Por qué access puede reemplazar un subárbol derecho antiguo?

El subárbol antiguo permanece conectado a través de fa como un padre en el camino representado; simplemente deja de ser preferido. Las relaciones de hijos auxiliares y las relaciones de padres de camino son independientes.

¿Se puede admitir la asignación en un camino?

Agrega una etiqueta de asignación que sobrescriba sumas más antiguas, actualice el valor y el máximo, y se componga con la reversión en un orden definido. El álgebra de etiquetas debe ser explícita y verificable.

¿Por qué es correcto findroot?

Después de access(x), propaga las etiquetas con push mientras sigues el hijo más a la izquierda hasta el nodo auxiliar más a la izquierda. Ese nodo es la raíz representada; aplícale splay para estabilizar operaciones posteriores.

¿Cuándo deberías evitar un link-cut tree?

Para un bosque estático, los recorridos DFS/Euler o la descomposición heavy-light son más simples. Para conectividad general en grafos dinámicos, concurrencia o persistencia, el límite de mantenimiento y el riesgo de implementación pueden superar el beneficio.