n nodes numbered 0 to n - 1, rooted at node 0. Its edges are listed in edges, where edges[i] = [a, b] connects nodes a and b. Node i holds a positive value values[i].
You may harvest any nodes you like: a harvested node adds its value to your score and drops to zero. Each node can be harvested at most once.
The tree must stay healthy: on every path from the root down to a leaf, the sum of values left after the harvest must be greater than zero.
Return the largest score you can collect while keeping the tree healthy.edges=[[0, 1], [0, 2], [2, 3]], values=[4, 6, 1, 3] → 10
Leave only the root (value 4) untouched and collect the rest: 6 + 1 + 3 = 10. Every root-to-leaf path starts with 4, so the tree stays healthy.
edges=[[0, 1]], values=[5, 2] → 5
Taking both nodes would zero out the path 0 → 1. It pays more to take the root (5) and leave the leaf with value 2.
n ≤ 2·10⁴edges.length = n - 1 and the edges form a treea, b < nvalues.length = nvalues[i] ≤ 10⁹edges=[[0, 1], [0, 2], [2, 3]], values=[4, 6, 1, 3]
10
Run checks the first 3 tests in your browser. Submit checks all 41 tests on the server, hidden ones included.