Root the tree at and process children before their parents. Let be the minimum number of paths covering the subtree of . Let be the minimum number of closed paths when one open path, with endpoint and value at its other endpoint, is left available for extension toward the parent. The open path itself is not counted.
For each child , define , and let . Ignore unattainable states. Compute
Let be the largest child gain , also considering when . Then
Keep negative gains as well.
Store each in a map keyed by . At , start with the temporary map and merge child maps one at a time. Before merging, use sums at common keys to update ; then keep the larger value at each key. Checking first prevents connecting two states from the same child. The final map represents , so add to all entries using a shared offset.
Always merge the smaller map into the larger one. With balanced search trees, the time complexity per case is and the space complexity is . The answer is .
Proof
A completed path containing uses zero, one, or two child edges. These choices make a singleton, close a child path with endpoint value , or join two child paths with the same endpoint value. Their costs are respectively , , and , giving the recurrence for .
An open path ending at uses at most one child, so . Substituting this into gives the second recurrence. Every transition constructs a valid cover, proving the DP optimal by induction.
Keeping only the largest gain per key preserves the best candidate to join with a new child. Combinations of two previously processed children are already recorded in .
For a smaller map of size , charge its merge work to disappearing entries if at least half are duplicates. Otherwise, charge it to surviving entries, whose containing map grows to at least . While an entry survives, its containing map never shrinks, and only one entry is initially created per vertex. Thus each entry receives total charge, giving entry visits.
