Watch 4 video solutions for Maximize Sum of Weights after Edge Removals, a hard level problem involving Dynamic Programming, Tree, Depth-First Search. This walkthrough by Aryan Mittal has 3,057 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.Problem Overview: You are given a weighted tree and must remove certain edges so the remaining structure satisfies a constraint while maximizing the total weight of the kept edges. The challenge is deciding which edges contribute positive value to the final structure without violating the rule on how many connections can remain.
Approach 1: Greedy Method Using Priority Queue (O(n log n) time, O(n) space)
This approach treats the tree as a dynamic programming problem over a depth-first search. Start from any root and compute the contribution each child edge provides to the total score. For every node, calculate the "gain" from keeping a child edge versus removing it. These gains are pushed into a priority queue so you can always pick the most valuable edges first. If the node can only keep a limited number of edges, you select the top gains and discard the rest. Sorting or a heap ensures the best contributions are chosen greedily. The DFS aggregates results bottom‑up, giving an optimal selection of edges. Time complexity is O(n log n) due to heap operations, and space complexity is O(n) for recursion and storage.
Approach 2: Kruskal's Algorithm with Modifications (O(E log E) time, O(n) space)
This approach reframes the problem as building a constrained maximum spanning structure. Sort all edges by weight in descending order, similar to Kruskal’s algorithm from graph theory. While processing edges, maintain connectivity and constraint conditions using a disjoint set union structure. Edges that violate the allowed structure or exceed node constraints are skipped. Because edges are processed from highest to lowest weight, the algorithm greedily preserves the most valuable ones first. The sorting step dominates the complexity at O(E log E), while union–find operations remain near constant time with path compression. Space complexity is O(n) for the DSU arrays.
Recommended for interviews: The DFS greedy approach is typically expected. It shows you understand dynamic programming on trees and how to combine it with greedy selection using sorting or heaps. Interviewers often look for the bottom‑up DFS that computes gains and selects the best contributions. The Kruskal-style solution is useful conceptually but appears less frequently in interviews because the tree DP formulation is more direct.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy DFS with Priority Queue | O(n log n) | O(n) | Best general solution for tree constraints where child contributions must be ranked and selected. |
| Modified Kruskal's Algorithm | O(E log E) | O(n) | Useful when modeling the problem as a constrained maximum spanning structure using union–find. |