Find branches within budget

MediumTreesDepth-first search

Each shelf stores stock[i] units. A branch rooted at a shelf contains that shelf and all of its descendants. Count how many branch totals are between lower and upper, inclusive. Count every qualifying root separately even when its branch overlaps another qualifying branch. 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], [2,3,5,7], 7, 10OUTPUT2

Branch 1 holds 3 + 7 = 10 and branch 3 holds 7. The other totals, 17 and 5, are outside the band.

Example 2

INPUT[-1,0,1], [0,0,0], 0, 0OUTPUT3

All three overlapping branches total zero, so all three roots qualify.

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.
0 <= lower <= upper <= 20,000,000,000; both bounds are integers.

Hint

A branch total is its own stock plus its child branch totals. Make sure children are finished before their parents.

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

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

INPUT[-1,0,0,1], [2,3,5,7], 7, 10

EXPECTED OUTPUT2

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