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.
This approach involves using a priority queue to manage the edges we can potentially remove. By sorting the edges initially based on their weights (descending), we can prioritize keeping higher-weighted edges in the final solution. The key here is to check the degree of each node after considering an edge and maintain the constraint that the degree doesn’t exceed k.
The Python solution uses a disjoint-set (union-find) to manage which nodes are connected while tracking the degree of each node. We iterate over the sorted edges and select the ones that do not violate the constraint k. The function returns the maximum sum of edge weights while adhering to the node degree constraint.
Time Complexity: O(n log n) due to sorting and the find-union operations.
Space Complexity: O(n) for the disjoint-set data structure and degree tracking.
This approach modifies the classic Kruskal's algorithm. Instead of focusing solely on forming a minimum spanning tree, the algorithm attempts to form a tree while respecting the degree constraint by picking edges starting from the one with the highest weight.
The Java implementation adapts Kruskal's strategy to build a subset of maximal weighted edges without exceeding the node degree limitations. By processing edges from the highest weight to the lowest, it effectively manages to keep the subset's total weight as large as possible.
Time Complexity: O(n log n) mainly from sorting and union-find operations.
Space Complexity: O(n) for the union-find structure and degree tracking.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Method Using Priority Queue | Time Complexity: O(n log n) due to sorting and the find-union operations. Space Complexity: O(n) for the disjoint-set data structure and degree tracking. |
| Approach 2: Kruskal's Algorithm with Modifications | Time Complexity: O(n log n) mainly from sorting and union-find operations. Space Complexity: O(n) for the union-find structure and degree tracking. |
| 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. |
3367. Maximize Sum of Weights after Edge Removals | DP on Trees | Memoization • Aryan Mittal • 3,057 views views
Watch 3 more video solutions →Practice Maximize Sum of Weights after Edge Removals with our built-in code editor and test cases.
Practice on FleetCode