339. Best Path from Root to Leaf
Print the largest total obtainable by starting at the root and walking down to some leaf, adding every value along the way.
The path must end at a LEAF. Stopping early at an internal node is not allowed, which matters when values are negative: the best path may have to walk through a loss to reach the leaf beyond it.
Carry the running total down and compare only when you arrive at a leaf. Every value on the path is included, including the root's.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print one integer, the largest root-to-leaf total.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.