TopCoder - SRM 144 - Div 2 - 1100 Pt

From Single Round Match No. 144 of TopCoder's Algorithm Competition:
Write a method estimateTimeOut that, given an edge-weighted tree, returns the minimum cost to visit all nodes. [Plus some backstory about a power outage, underground transformers, and a catacombic sewer.]
(Full problem specification is copyright TopCoder; and, can be found in the TopCoder problem archives.)

Solution.
Unit Tests For Sample Data.

This problem was used as the Division 2 1100-point problem. It reminds me of certain ACM-ICPC problems: mix two parts strong underlying data structure and algorithm with one part playful, semi-verbose problem description.

The solution to the problem is to realize that each edge in the tree will need to be traversed twice (once to go to a node, and once to come back from it) in order to visit all nodes, except for the edges on the path to the last visited node. Therefore, the minimum cost can be calculated by finding the most expensive node to reach (from the tree's root), and subtracting the cost reaching that node from twice the sum of all edge weights.