Finde das Zentrum eines Baumes
Du hast
n Städte gegeben, die durch n-1 Straßen miteinander verbunden sind. Alle Städte sind über direkte oder indirekte Verbindungen erreichbar. Du möchtest sicherstellen, dass die Hauptstadt an der bestmöglichen Stelle liegt.Der beste Standort ist deiner Meinung nach derjenige, bei dem der größte Abstand zu den Randstädten (Städten, die nur an eine andere Stadt angebunden sind) möglichst gering ausfällt. Welche Städte wären also die besten Kandidaten für die Hauptstadt?
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
v (1 ≤ v ≤ 100 000).In den folgenden
v-1 Zeilen stehen jeweils zwei ganze Zahlen v1 und v2 (1 ≤ v1, v2 ≤ v), was bedeutet, dass die Stadt v1 mit der Stadt v2 und umgekehrt verbunden ist.Ausgabe
Das Programm soll die besten Kandidaten für die Hauptstadt in aufsteigender Reihenfolge ausgeben.
Beispiele
Eingabe | Ausgabe |
4
1 2
2 3
3 4 | 2 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB