FastPrep
Problem · Tree

Best Sum Downward Tree Path

Learn this problem
● MediumCitadelNEW GRADOA

Problem statement

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₁, u₂, u₃, ..., uₖ where each node uᵢ is a child of node uᵢ₋₁ for 1 < i ≤ k. For example, given the following tree (labeled node number/value):

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.

Function

bestSumDownwardTreePath(parent: int[], values: int[]) → int

Complete the function bestSumDownwardTreePath in the editor with the following parameter(s):

  1. int parent[n]: each parent[i] represents the parent node for node i, parent[i] = -1 means node i is the root
  2. int values[n]: each values[i] represents the value of node i

Returns

int: the largest sum of values along a path down the tree from any node u

Examples

Example 1

parent = [-1, 0, 1, 2, 0]values = [5, 7, -10, 4, 15]return = 20
The downward path 0 → 4 has value sum 5 + 15 = 20, which is greater than every other downward path.

Constraints

  • 1 ≤ n ≤ 10⁵
  • parent[0] = -1
  • 0 ≤ parent[i] < n for 0 < i < n
  • -1000 ≤ values[i] ≤ 1000
  • the tree described is valid

More Citadel problems

drafts saved locally
public int bestSumDownwardTreePath(int[] parent, int[] values) {
  // write your code here
}
parent[-1, 0, 1, 2, 0]
values[5, 7, -10, 4, 15]
expected20
checking account