Den Durchmesser eines Baumes bestimmen
Sie haben einen Baum mit
v Knoten, und Ihre Aufgabe ist es, den Durchmesser dieses Baumes zu ermitteln. Der Durchmesser bezeichnet die Länge des Pfads zwischen den beiden am weitesten voneinander entfernten Knoten.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, v2 (1 ≤ v1, v2 ≤ v), die anzeigen, dass der Knoten v1 mit dem Knoten v2 verbunden ist und umgekehrt.Ausgabe
Das Programm soll den Durchmesser des gegebenen Baumes ausgeben.
Beispiele
Eingabe | Ausgabe |
3
1 2
1 3 | 2 |
5
1 2
1 3
3 4
3 5 | 3 |
Tipp 1
Man kann DFS (Tiefensuche) mehrmals von verschiedenen Ausgangsknoten aus durchführen.
Tipp 2
Man kann eine DFS (Tiefensuche) von Knoten 1 aus starten und den am weitesten entfernten Knoten finden (da es sich um einen Baum handelt und keine Zyklen existieren, ist das ohne BFS möglich).
Anschließend führt man von dem gefundenen am weitesten entfernten Knoten eine weitere DFS durch, um den davon aus gesehen am weitesten entfernten Knoten zu bestimmen.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB