Finde das Centroid eines Baums
Du hast einen Baum mit
v Knoten gegeben und deine Aufgabe besteht darin, das Centroid dieses Baums zu bestimmen. Ein Centroid eines Baums ist ein Knoten, der, wenn man ihn entfernt, alle verbleibenden Teilbäume höchstens Knoten haben.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
v (1 ≤ v ≤ 100 000).Die folgenden
v-1 Zeilen enthalten jeweils ein Paar ganzer Zahlen v1, v2 (1 ≤ v1, v2 ≤ v). Diese Angabe bedeutet, dass der Knoten v1 mit dem Knoten v2 verbunden ist und umgekehrt.Ausgabe
Das Programm soll das Centroid des gegebenen Baums ausgeben. Falls es mehrere gültige Lösungen gibt, darf eines davon ausgegeben werden.
Beispiele
Eingabe | Ausgabe |
3
1 2
1 3 | 1 |
5
1 2
2 3
3 4
3 5 | 3 |
Tipp
Du kannst für jeden Knoten die Größe seines Teilbaums berechnen (also die Anzahl der Kindknoten).
Anschließend überprüfst du bei jedem Knoten seine Teilbäume, ob deren Größe kleiner oder gleich der Hälfte der Knoten im gesamten Baum ist (also alle Kindknoten und
v - currentNodeSize für den übergeordneten Teilbaum).Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB