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