|
|
back to boardCan somebody give me some hints on how to solve P1056? Posted by abc 6 Feb 2003 11:58 Re: Can somebody give me some hints on how to solve P1056? 1. the graph forms a tree
2. you need to give this tree direction (since the given tree is
undirected)
3. the longest path starting at node k is the maximum of 2 values:
the maximum path starting at k and going DOWN (a tree has no cycles
so you can solve this easily in linear time, i used simple DP)
and the maximum path by going UP from k. Re: Can somebody give me some hints on how to solve P1056? "the maximum path by going UP from k."
What do you mean by this? Re: Can somebody give me some hints on how to solve P1056? How to calculate the maximum path by going up from k Re: Can somebody give me some hints on how to solve P1056? Just invert directions of all edges and calculate the maximum path by going DOWN form k. Realization of this thing is much easier than its description. Re: Can somebody give me some hints on how to solve P1056? Posted by Sid 24 Jun 2005 11:47 Just cut off leafs of tree step by step while count of nodes >2!
Edited by author 25.06.2005 14:44 Re: Can somebody give me some hints on how to solve P1056? Far not the fastest solution, but passed (0.375 sec):
1. make a bidirectional graph, connectivity of which will be kept in an array of vectors
2. start dfs from each of the verticies which are not leaves and calculate the longest path
3. Note that if there are 2 vertices, the answer is always "1 2"
The solution might run in O(N*(N+M)) time, as I guess
Edited by author 15.02.2010 13:13
Edited by author 15.02.2010 13:13 |
|
|
