Company: Citadel_19sep
Difficulty: medium
Best Sum Downward Tree Path Problem Description For a tree with n nodes rooted at node 0 (nodes numbered from 0 to n-1 ), where each node i has a value given by values[i] , determine the maximum sum of values along any path that starts at a node u and only goes downward in the tree. Consider only paths of the form u 1 , u 2 , ..., u k where each node u i is a child of node u i-1 for 1 < i <= k . For example, given the following tree (labeled node number / value): 0/5 / \ 1/7 4/15 / 2/-10 / 3/4 Two possible paths are 0 → 1 → 2 → 3 which has a sum of 5 + 7 + (-10) + 4 = 6 and 1 → 2 → 3 with a sum of 7 + (-10) + 4 = 1 . The highest sum path is 0 → 4 with a sum of 5 + 15 = 20 . Complete the function bestSumDownwardTreePath in the editor with the following parameter(s): int parent[n] : each parent[