Encontrar o Diâmetro de uma Árvore
Você tem uma árvore com
v vértices e o seu objetivo é determinar o diâmetro dessa árvore. O diâmetro é o comprimento do caminho entre os dois vértices mais afastados.Entrada
A primeira linha da entrada contém um único inteiro
v (1 ≤ v ≤ 100 000).As
v-1 linhas seguintes contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), significando que o vértice v1 está conectado ao vértice v2 e vice-versa.Saída
O programa deve apresentar o diâmetro da árvore fornecida.
Exemplos
Entrada | Saída |
3
1 2
1 3 | 2 |
5
1 2
1 3
3 4
3 5 | 3 |
Dica 1
Pode realizar DFS (Depth First Search) várias vezes, partindo de diferentes vértices.
Dica 2
Pode iniciar uma DFS a partir do nó 1 para encontrar o vértice mais distante (como é uma árvore e não há ciclos, não há necessidade de BFS).
Depois, comece uma nova DFS a partir desse vértice encontrado para identificar qual é o vértice mais distante dele.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB