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
|
ktcoder:
2018-06-22 11:39:54
It just requires single dfs.
|
|
dikshit_30:
2018-06-19 18:31:02
Logic: Use two bfs. The first to find the farthest node from a particular node. That will be the leaf node. Again applying bfs on this will give you the maximum distance. |
|
shivamgarg1901:
2018-05-25 11:00:13
If your approach is correct you not need to worry about the root of the tree.
|
|
yaswanth desu:
2018-04-10 04:45:17
If any one having doubt regarding the root means, consider the below example
|
|
saiyaman_098:
2018-04-09 20:48:03
What's the bfs+dp approach? |
|
rahuldcoder:
2018-03-17 15:32:31
Why running two dfs solves the problem.I still do not get it. |
|
hsmfawaz:
2018-03-14 03:02:36
Its a Tree diameter problem so you have 2 solutions to get AC with oneshot
|
|
hai_dee:
2018-03-10 04:24:25
Yay AC in one go Python, using a single BFS + DP approach :D Fun problem! |
|
kartik_354:
2018-02-02 14:22:24
the test cases of this question are weak..plz correct them..
|
|
bani_raheja:
2018-01-03 21:25:31
First did it in around september when I had no knowledge of DP, by using two BFS. Did it again with dp in January. Trust me, you'd love the DP idea. It's much more reliable than 2 BFSs. |
| 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 |
RSS