Finding the lightest simple path in trees with integer weights
Order the tree, so we can speak about a node and its subtrees. Now evaluate the tree recursively. In each node keep track of two values: (1) the value of the optimal path below the node (starting and ending somewhere below in the subtrees), and (2) the value of the optimal path below that additionally ends in the node itself.