Minimum Tree Value After Leaf Relocations

You are given an undirected tree with n nodes, rooted at node 1. Node i has the positive value values[i - 1].
You may perform at most k operations. In one operation:
Choose a non-root leaf in the current rooted tree.
Disconnect it from its parent and reconnect it as a child of any remaining node, including its former parent.
A node that becomes a leaf after earlier operations may be chosen in a later operation. The root itself is never moved.
After all operations, define the value of every node to be the sum of the original assigned values of all nodes in its final rooted subtree, including itself. Return the minimum possible sum of these final node values.
The answer can exceed the range of a 32-bit integer.

Function
minimumTreeValue(n: int, k: int, values: int[], edges: int[][]) → long

Examples
Example 1
n = 4
k = 1
values = [5,1,4,2]
edges = [[1,2],[2,3],[2,4]]
return = 21
Before any move, the total is 25. Move leaf 3 directly under the root. Its depth decreases from 2 to 1, reducing the total by 4. The resulting minimum is 21.
Example 2
n = 5
k = 3
values = [1,10,1,10,10]
edges = [[1,2],[2,3],[2,4],[4,5]]
return = 63
Move node 5, then the newly created leaf 4, and also move leaf 3, attaching each one to the root. The total decreases from 94 to 63.
Example 3
n = 1
k = 0
values = [7]
edges = []
return = 7
The tree contains only the root, so no operation is possible and its final subtree sum is 7.

Constraints
1 <= n <= 1000
0 <= k <= n - 1
values.length == n
1 <= values[i] <= 10^9
edges.length == n - 1
Every edge is a pair [u, v] with 1 <= u, v <= n.
edges forms a valid undirected tree.

Rewrite the objective first. A node's value counts once for every ancestor including itself, so the total equals the sum of values[i] * depth(i), with the root at depth 1. Moving a leaf directly under the root sets its depth to 2, which is the best any non-root node can get. Gain for a node is values * (depth - 2) when you move it. Run a DFS to get depths. The catch is the order: a node can only move after its children are gone, and moving a leaf doesn't change other nodes' depths except its own subtree, which is empty. So pick the k nodes with the biggest positive gain, but check that the parent-before-child constraint holds, since a deeper node is moved first and that's always allowed. Sort the gains, take the top k, subtract. Use 64-bit math. Verify with example 1: gain 4 * 1 = 4, giving 21. StealthCoder is your hedge if the reformulation slips away live.

Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.