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.

"the maximum path by going UP from k."

What do you mean by this?

How to calculate the maximum path by going up from k

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.

Just cut off leafs of tree step by step while count of nodes >2!


Edited by author 25.06.2005 14:44

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