Maximum length path between any two nodes in a tree with possible negative edge weights
You can find this path in linear time:


If the tree is unrooted, pick an arbitrary node as root.
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.