The Heaviest Subtree
Each node of a tree holds a value, which may be negative. The tree is rooted at node 1, and a node's SUBTREE is that node together with everything below it.
Print the largest total value any one of the n subtrees has.
4 nodes, values 3 -2 1 5, edges 1-2 1-3 3-4 -> 7 the subtree at node 3
1 node, value -7 -> -7
## One sweep
sub[u] = value[u] + sum over children c of sub[c]
and the answer is the largest sub[u] over all u. That is the entire algorithm.
The recurrence is short because a subtree's total is determined by its children's totals and nothing else: no choice is made anywhere, which is optimal substructure in its plainest form.
## Where negative values change things
With every value at least 0, the whole tree is always at least as good as any part, and the
answer is just sub[root]. Here that is false: the first sample answers 7, not 7 from the
root, and negative branches can make a strict subtree the best.
Three things follow, and all three are tested:
· you must take the maximum over ALL nodes, not just the root · you may NOT drop a negative child, because a subtree is the whole of what hangs below a node, not a chosen part of it · the starting value of the running maximum may not be 0, since every subtree can be negative and 0 is not an available answer
The second point is the one worth dwelling on. This looks like the array problem where a running total is reset whenever it turns negative, and it is not: there is no empty subtree to fall back to, so nothing is ever discarded.
## Boundaries
All values negative: the answer is the largest single leaf value, or whichever node's whole subtree is least bad. The tests include a case where the best is a negative number.
All values zero: the answer is 0.
## Cost
Time O(n). Space O(n).
Totals reach 100000 times 10^9 in magnitude, so use 64 bits.