356. Best Path Anywhere
Print the largest total obtainable along any path in the tree. The path may start and end at ANY two nodes, need not touch the root, and may bend once at its highest point.
This is the hardest problem in the topic, and it is hard because each node has to answer two different questions at once:
1. What is the best path that BENDS here, going down into both subtrees? That is
value + bestLeft + bestRight, and it is a candidate for the answer.
2. What is the best path that goes down through here and CONTINUES upwards? That
is value + max(bestLeft, bestRight), and it is what the parent needs.
Only the second is returned; the first updates a running best.
Negative subtrees are the other half. If a subtree's best contribution is negative, take 0 instead and leave it out of the path. A tree of entirely negative values then answers with its single largest value, which the negative test checks.
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 total along any path.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.