Minimum Tree Value After Leaf Relocations
Updated
Problem statement
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[][]) → longExamples
Example 1
n = 4k = 1values = [5,1,4,2]edges = [[1,2],[2,3],[2,4]]return = 21Before 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 = 5k = 3values = [1,10,1,10,10]edges = [[1,2],[2,3],[2,4],[4,5]]return = 63Move 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 = 1k = 0values = [7]edges = []return = 7The tree contains only the root, so no operation is possible and its final subtree sum is 7.
Constraints
1 <= n <= 10000 <= k <= n - 1values.length == n1 <= values[i] <= 10^9edges.length == n - 1- Every edge is a pair
[u, v]with1 <= u, v <= n. edgesforms a valid undirected tree.
More Google Online Assessment questions
- Book Reading EveningsOA · Seen Nov 2026
- Count Score CategoriesOA · Seen Nov 2026
- Minimum Cars for Rental RequestsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Shortest Path in a Binary MatrixOA · Seen Nov 2026
- Robot Assembly Line ConflictsOA · Seen Oct 2026
- Assign LockerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Biggest Number From DigitsOA · Seen Oct 2026
- Consolidate On-Call RotationsOA · PHONE SCREEN · Seen Oct 2026
- Decreasing SubsequencesOA · Seen Sep 2026
- Minimize Absolute Difference of Server LoadsOA · Seen Sep 2026
Similar questions at other companies
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
- Binary Tree CamerasAmazon · OA · PHONE SCREEN
- Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
- Tree PointsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions
- Binary Tree Maximum Path SumArcesium · OAArcesium interview questions
- Tree Node With Maximum BeautyC3.ai · OAC3.ai interview questions
- Best Sum Downward Tree PathCitadel · OACitadel interview questions
- Longest Alternating a/b Path in a TreeHudson River Trading · OAHudson River Trading interview questions
- Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions