FastPrep
Problem · Tree

Best Sum Downward Tree Path

● MediumCitadelNEW GRADOA

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 Description

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
01 · Example 1
capacity = [9, 3, 3, 3, 9]
return = 2
There are 2 stable subsegments: [3, 3, 3] and [9, 3, 3, 3, 9]. Return 2.
Constraints
  • 1 ≤ n ≤ 10⁵
  • parent[0] = -1
  • 0 ≤ parent[i] < n-1 for 0 < i < n-1
  • -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
}
capacity[9, 3, 3, 3, 9]
expected2
sign in to submit