Trouver le centre d’un arbre
On vous donne
n villes reliées entre elles par n-1 routes. Toutes les villes sont connectées (éventuellement en passant par d’autres). Vous souhaitez placer la capitale au meilleur endroit possible.Vous décidez que la position idéale est celle qui minimise la plus grande distance avec les villes situées en bordure (celles qui ne sont reliées qu’à une seule autre ville). Quelles villes seraient donc les meilleures candidates pour devenir la capitale ?
Entrée
La première ligne de l’entrée contient un entier
v (1 ≤ v ≤ 100 000).Les
v-1 lignes suivantes contiennent des paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v), indiquant que le sommet v1 est connecté au sommet v2 (et inversement).Sortie
Le programme doit afficher les meilleurs candidats pour la capitale dans l’ordre croissant.
Exemples
Entrée | Sortie |
4
1 2
2 3
3 4 | 2 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB