Encontrar el centro de un árbol
Se te dan
n ciudades que están conectadas entre sí mediante n-1 carreteras. Todas las ciudades están comunicadas (posiblemente a través de otras ciudades). Quieres asegurarte de que la capital se ubique en la mejor posición posible.Decides que la mejor ubicación es aquella que minimiza la distancia máxima hacia las ciudades fronterizas (las ciudades que solo están conectadas con una ciudad). ¿Qué ciudades serían las mejores candidatas para convertirlas en capital?
Entrada
La primera línea de la entrada contiene un único entero
v (1 ≤ v ≤ 100 000).Las siguientes
v-1 líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v), lo cual significa que el vértice v1 está conectado con el vértice v2 y viceversa.Salida
El programa debe imprimir los mejores candidatos a la capital en orden creciente.
Ejemplos
Entrada | Salida |
4
1 2
2 3
3 4 | 2 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB