Maximum Root-to-Leaf Score
Problem statement
Each node of a rooted tree has a score. Return the largest sum along a path that starts at the root and ends at a leaf, counting both endpoints.
Node i has score scores[i] and parent parents[i]. The root is node 0, whose parent is -1. A node may have any number of children. A leaf has no children. Parent indices need not be smaller than child indices.
You must reach a leaf, even when scores are negative. A single-node tree returns that node's score. An empty tree returns 0. Use a 64-bit result.
Function
maxRootLeafScore(scores: int[], parents: int[]) → longExamples
Example 1
scores = [5,4,9,-2,8]parents = [-1,0,0,1,1]return = 17The root-to-leaf scores are 5 + 4 - 2 = 7, 5 + 4 + 8 = 17, and 5 + 9 = 14. Their maximum is 17.
Example 2
scores = [-5,-2,-8]parents = [-1,0,0]return = -7The two complete paths score -5 - 2 = -7 and -5 - 8 = -13. Stopping at the root is not allowed because it has children, so the answer is -7.
Example 3
scores = []parents = []return = 0The tree is empty, so the defined result is 0.
Constraints
0 <= scores.length <= 5000scores.length == parents.length-1000000 <= scores[i] <= 1000000-1 <= parents[i] <= 4999- For nonempty input,
parents[0] == -1; every other parent is a valid node index. The parent links form one tree rooted at node0, with no cycle.