Maximum length path between any two nodes in a tree with possible negative edge weights

Problem Detail: 

Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a graph with edge weights 1 but that won't work here.

All I can think of is going for a $O(N^2)$ approach with LCA but thats a glaringly bad approach for huge trees ($N \sim 100000$)

Asked By : NitinJ

Answered By : FrankW

You can find this path in linear time:

1. If the tree is unrooted, pick an arbitrary node as root.

2. Traverse the tree in postorder and for each node:

   2.1. Find the longest and second longest path ending in the current node by maximizing over all children and extending the longest path ending in the child by the edge between parent and child.
   If there are no two children that result in paths of positive length, set the second longest (and if necessary also the longest) path as starting and ending here (length 0).

   2.2. Find the longest path in the subtree that starts at the current node by maximizing over the longest paths in all subtrees below the current one and the path resulting from joining the two paths found in the previous step.

Now the longest path in the subtree started at the root is the one you are looking for.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27935