Skip to Content
CTRL K

At Large

Análisis oficial (C++) 

Solución (O(NN)O(N\sqrt N))

Véase el comentario de Eric Zhang .

Solución alternativa (falsa)

Primero escribimos alguna DP O(N2)\mathcal{O}(N^2) que de algún modo es lo suficientemente rápida como para pasar los casos de prueba 1-6.

Código

Esto no funcionará para los casos de prueba 7-11, ¡pero estos casos de prueba son bastante especiales!

¿Por qué?

En estos casos de prueba los árboles tienen a lo sumo 20 hojas. Por lo tanto basta comprimir las aristas del árbol (quitar repetidamente vértices de grado 2) y ejecutar la misma solución.

Fundamentos