Watch 10 video solutions for Maximize Sum of Weights after Edge Removals, a hard level problem. This walkthrough by NeetCode has 452,961 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with weight wi in the tree.
Your task is to remove zero or more edges such that:
k other nodes, where k is given.Return the maximum possible sum of weights for the remaining edges after making the necessary removals.
Example 1:
Input: edges = [[0,1,4],[0,2,2],[2,3,12],[2,4,6]], k = 2
Output: 22
Explanation:
[0, 2, 2], ensuring that no node has edges with more than k = 2 nodes.Example 2:
Input: edges = [[0,1,5],[1,2,10],[0,3,15],[3,4,20],[3,5,5],[0,6,10]], k = 3
Output: 65
Explanation:
k = 3 nodes, we don't remove any edges.
Constraints:
2 <= n <= 1051 <= k <= n - 1edges.length == n - 1edges[i].length == 30 <= edges[i][0] <= n - 10 <= edges[i][1] <= n - 11 <= edges[i][2] <= 106edges form a valid tree.