352. Minimum Operations to Remove All Nodes

Minimum Operations to Remove All Nodes

You are given a tree rooted at node 1. Every node i has a positive value nodeValues.get(i - 1).

In one operation, choose any currently alive node u and decrease the value of every currently alive node in the subtree of u by k.

A node is removed when its value becomes less than or equal to 0. Removing a node disconnects its surviving child subtrees into separate components. Future operations cannot pass through a removed node.

Return the minimum number of operations required to remove every node.

Method Signature

long minimumOperations(List<Integer> nodeValues, List<String> edges, int k)

Parameters

nodeValues contains the initial node values, where nodeValues.get(i - 1) is the value of node i.
edges describes the rooted tree. Each string has the format "parent,child" and represents a direct edge from parent to child.
k is the amount subtracted from each affected node in one operation.

Return Value

Return the minimum number of operations needed to remove all nodes from the tree.

Operation Rules

The selected node u must currently be alive.
The operation affects u and all alive descendants connected to it through alive nodes.
All affected values are decreased simultaneously before nodes are removed.
Surviving children of a removed node become roots of separate components.

Constraints

1 <= nodeValues.size() <= 100,000
edges.size() = nodeValues.size() - 1
1 <= nodeValues.get(i) <= 1,000,000,000
1 <= k <= 1,000,000,000
1 <= parent, child <= nodeValues.size()
parent != child
Node 1 is the root.
Every node except node 1 has exactly one parent.
The given edges form one valid rooted tree.

Examples

Example 1

minimumOperations(nodeValues = List.of(5, 9, 3, 12, 6), edges = List.of("1,2", "1,3", "2,4", "2,5"), k = 3)

Output: 4

Two operations at node 1, one at node 2, and one at node 4 remove every node. No sequence can use fewer than four operations.

Example 2

minimumOperations(nodeValues = List.of(8, 2, 11), edges = List.of("1,2", "2,3"), k = 3)

Output: 6

The first operation at node 1 removes node 2, disconnecting node 3. Removing the remaining components requires five additional operations.

Example 3

minimumOperations(nodeValues = List.of(7, 5, 1, 7), edges = List.of("1,2", "1,3", "1,4"), k = 4)

Output: 2

Applying two operations at node 1 removes the root and all three of its children.

Example 4

minimumOperations(nodeValues = List.of(13), edges = List.of(), k = 5)

Output: 3

The tree contains only its root, whose value becomes non-positive after three operations.