Count the end-shelf stock

EasyTreesArrays

The brewery stores ingredients on a branching shelf system. A leaf is a shelf with no children. Return the sum of stock[i] only at leaf shelves; stock on internal shelves does not count. A single shelf is itself a leaf. The tree has nodes numbered 0 through n - 1. parent[0] is -1; every other parent[i] is the parent of node i. The tree is connected and has no cycles. Node numbers do not imply traversal order: a parent may have a larger number than its child.

Example 1

INPUT[-1,0,0,1], [50,20,4,7]OUTPUT11

Shelves 2 and 3 have no children, so only their 4 + 7 units count.

Example 2

INPUT[-1], [9]OUTPUT9

The only shelf has no children and is therefore a leaf.

Keep in mind

1 <= n = parent.length <= 20,000
parent[0] = -1; all other parent entries are valid node indices describing one rooted tree.
stock.length = n; each stock amount is an integer from 0 to 1,000,000.

/** @returns {number} */
function solve(parent, stock) {
  // Return the result described above.
}

/** @returns {number} */
function solve(parent, stock) {
  // Return the result described above.
}

INPUT[-1,0,0,1], [50,20,4,7]

EXPECTED OUTPUT11

Public samples only. These checks do not award ranked points.

AFTER THE SOLVE

How the solution works.

Walk through a solution, check its time and space costs, and compare it with yours.

Checking your progress…

Count the end-shelf stock

Example 1

Example 2

Keep in mind

How the solution works.

Related problems

Load the trays by tier

Find branches within budget