Minimum Server Leaf Removals
MediumTrees · Cisco
Servers 1 to n form a tree rooted at server 1. Each element of edges is [parent, child, weight]: child is directly below parent, and the link has an integer weight (possibly negative). Server v has a load limit limits[v - 1].
For a server v and one of its ancestors u (any server on the path from the root down to v, excluding v itself), let dist(u, v) be the sum of the weights on the path from u down to v. Server v is overloaded if dist(u, v) > limits[v - 1] for at least one ancestor u. The root has no ancestors, so it is never overloaded.
You may decommission servers, but only leaves: a server can be removed only when none of its children remain. You may repeat this, so removing all of a server's children makes it a leaf that can then be removed.
Return the minimum number of servers you must decommission so that no remaining server is overloaded.
Example 1
- Input:
- n = 7, edges = [[1, 2, 3], [1, 3, -2], [2, 4, 4], [2, 5, -6], [3, 6, 5], [6, 7, 1]], limits = [10, 2, 5, 6, 9, 6, 5]
- Output:
- 4
- Explanation
- Server 2 is 3 below the root, over its limit of 2, so it must go, and removing it first requires removing its leaves 4 and 5. For server 7, the path from server 3 has sum 5 + 1 = 6, over its limit of 5 even though the path from the root is only 4. That makes 3 + 1 = 4 removals.
Example 2
- Input:
- n = 3, edges = [[1, 2, -5], [2, 3, 4]], limits = [1, 1, 3]
- Output:
- 1
- Explanation
- From the root, server 3 is at -5 + 4 = -1, but from server 2 it is 4 below, over its limit of 3. Removing leaf 3 is enough; server 2 is at -5 and is fine.
Example 3
- Input:
- n = 1, edges = [], limits = [5]
- Output:
- 0
- Explanation
- A single root server is never overloaded, so nothing is removed.
Constraints
1 <= n <= 10^5edges.length == n - 1, and the edges form a tree rooted at1(each server other than1has exactly one parent).-10^9 <= weight <= 10^91 <= limits[i] <= 10^9