| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
||||||||||||||
|
2021-04-09 21:24:19
@wiseman_123 - How can you say that space is O(1) What about visited array and adjacency list ? |
||||||||||||||
|
2021-02-24 19:19:39
time - O(N). Space - O(1). |
||||||||||||||
|
2020-12-30 13:17:44
AC in one GO double BFS (0.01s) :) Last edit: 2020-12-30 13:18:06 |
||||||||||||||
|
2020-09-22 10:12:46
just use the diameter of a tree concept. you're good to go then! |
||||||||||||||
|
2020-09-11 17:49:08
this is a problem of ....finding diameter of tree |
||||||||||||||
|
2020-08-02 22:56:09
AC in one go, dp on trees. |
||||||||||||||
|
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. |
||||||||||||||
|
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) |
||||||||||||||
|
2020-06-22 20:37:33
Do not print a new line at the end of the ans. |
||||||||||||||
|
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. |
||||||||||||||
RSS