PT07Z - Longest path in a tree


You are given an unweighted, undirected tree. Write a program to output the length of the longest path (from one node to another) in that tree. The length of a path in this case is number of edges we traverse from source to destination.

Input

The first line of the input file contains one integer N --- number of nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges of that tree --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u, v <= N).

Output

Print the length of the longest path on one line.

Example

Input:
3
1 2
2 3

Output:
2

hide comments
sabbir0152: 2020-09-11 17:49:08

this is a problem of ....finding diameter of tree

lm10_piyush: 2020-08-02 22:56:09

AC in one go, dp on trees.

amitk766: 2020-07-07 15:56:58

Run dfs/bfs two times , in the first run find the farthest vertex from vert 1, and the again run dfs from that vertex(farthest) and calculate the longest path.

sarveshjain967: 2020-06-25 13:37:47

AC in one go. Remember what constitutes the longest path:
1. One more than the longest path below the node
2. largest ever = max("two long paths below the node", largest ever)

zegatron: 2020-06-22 20:37:33

Do not print a new line at the end of the ans.

zegatron: 2020-06-22 20:35:21

I am getting wrong answer on my code. I call bfs for each node. and take the maximum depth.

saurabhshadow: 2020-05-29 20:42:24

If you still stuck at this:
Here is a hint:
- Find the maximum depth node from any node.

nature95: 2020-05-14 13:03:23

Used bfs two times.

offamitkumar: 2020-05-04 19:33:55

AC in single graph traversal . Just keep track of 3 things :
1. Best answer if we don't consider current as root.
2. Best answer if we consider current node as root. i.e. current node connecting two of it's child
3. Best child found till now of current node as this is n-ary tree.

gnuzinhoo: 2020-05-02 16:05:00

I solved it using two bfs


Added by:Thanh-Vy Hua
Date:2007-03-28
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Co-author Amber