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
:.Mohib.::
2015-09-17 17:00:47
Nice...!! |
|
[Mayank Pratap]:
2015-09-16 15:54:02
Good prob to increase confidence in tree.. :) |
|
Guilherme Sena:
2015-09-08 05:36:36
@Nitesh Tiwari : That is not a tree. (1,2,3,11) is a cycle since edges are undirected. |
|
Pratik:
2015-08-31 12:08:54
Very good problem with a simple solution |
|
ramjeet saran:
2015-08-22 14:25:59
not a binary tree, cost me 3 WA |
|
Khanh Ninh:
2015-08-11 14:35:51
Dynamic Program + DFS , Advanced Solution. |
|
mohit:
2015-08-04 20:54:44
DFS! diameter of a tree . http://www.geeksforgeeks.org/diameter-of-a-binary-tree/
|
|
sameer Hussain:
2015-07-30 22:00:44
is it a binary tree or any random tree ??
|
|
Nitesh Tiwari:
2015-07-25 23:25:25
Answer for the below test case is 6, spojtoolkit is showing 5, I got it accepted with 6.
|
|
Krzysztof Strojny:
2015-07-22 11:03:16
This can be done in in one loop over vertices, take advantage that this is a tree, no need for BFS or DFS |
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 |