Encontrar el diámetro de un árbol
Se te proporciona un árbol con
v vértices y tu tarea es encontrar el diámetro del árbol. El diámetro es la longitud del camino más largo entre los dos vértices más distantes.Entrada
La primera línea de la entrada contiene un solo número entero
v (1 ≤ v ≤ 100 000).Las siguientes
v-1 líneas contienen pares de números enteros v1, v2 (1 ≤ v1, v2 ≤ v), lo que indica que el vértice v1 está conectado con el vértice v2 y viceversa.Salida
El programa debe imprimir el diámetro del árbol dado.
Ejemplos
Entrada | Salida |
3
1 2
1 3 | 2 |
5
1 2
1 3
3 4
3 5 | 3 |
Hint 1
Puedes realizar DFS varias veces desde diferentes nodos iniciales.
Hint 2
Puedes realizar DFS empezando desde el nodo 1 y encontrar el vértice más lejano (como esto es un árbol y no hay ciclos, podemos hacerlo sin BFS).
Luego, inicia otra DFS desde ese vértice más lejano para hallar el vértice más distante a partir de él.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB