Algorithms and Data Structures

Find the Diameter of a Tree

You are given a tree with v vertices and your task is to find the diameter of the tree. The diameter is the length of the path between the two furthermost vertices.


The first line of the input contains a single integer v (1 ≤ v ≤ 100 000).
The following v-1 lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.


The program should print the diameter of the given tree.


3 1 2 1 3
5 1 2 1 3 3 4 3 5
Hint 1
You can perform DFS multiple times from different sources
Hint 2
You can perform DFS starting from node 1 and find the furthermost vertex (as this is a tree, meaning there are no cycles, we can do that without BFS).
Then start a DFS from the found furthermost vertex and find the farthest vertex from that one.


Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue