Trovare il Diametro di un Albero
Ti viene fornito un albero con
v vertici. Il tuo obiettivo è determinare il diametro di questo albero, ovvero la lunghezza del percorso che collega i due vertici più distanti.Input
La prima riga dell'input contiene un singolo intero
v (1 ≤ v ≤ 100 000).Le successive
v-1 righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v) che indicano che il vertice v1 è collegato al vertice v2 e viceversa.Output
Il programma deve stampare il diametro dell’albero fornito.
Esempi
Input | Output |
3
1 2
1 3 | 2 |
5
1 2
1 3
3 4
3 5 | 3 |
Hint 1
È possibile eseguire più volte DFS da diverse sorgenti.
Hint 2
Puoi avviare una DFS dal nodo 1 per trovare il vertice più distante (dato che è un albero, quindi privo di cicli, è possibile farlo anche senza BFS).
In seguito, avvia di nuovo una DFS dal vertice più distante trovato e determina il vertice più lontano da quest’ultimo.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB