579. 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.

Constraints - `1 ≤ n ≤ 100000` - `-10^9 ≤ each value ≤ 10^9` - the input is always a tree