Encuentra el centroide de un árbol
Se te proporciona un árbol con
v vértices, y tu objetivo es encontrar el centroide de ese árbol. El centroide de un árbol es un vértice tal que, al eliminarlo, todos los subárboles que quedan tienen un tamaño de, como máximo, nodos.Entrada
La primera línea de la entrada contiene un solo entero
v (1 ≤ v ≤ 100 000).Las siguientes
v-1 líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v), lo que significa que el vértice v1 está conectado con el vértice v2 y viceversa.Salida
El programa debe imprimir el centroide del árbol dado. Si hay varias respuestas posibles, puede imprimir cualquiera de ellas.
Ejemplos
Entrada | Salida |
3
1 2
1 3 | 1 |
5
1 2
2 3
3 4
3 5 | 3 |
Pista
Puedes calcular el tamaño del subárbol de cada nodo (el número de nodos secundarios).
Luego, revisa todos los subárboles de cada nodo para verificar si su tamaño es menor o igual a la mitad de la cantidad total de vértices en el árbol (suma de todos los nodos secundarios y
v - currentNodeSize para tomar en cuenta el subárbol del padre).Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB