Maximize Sum of Weights after Edge Removals
HardPrompt
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:
- Each node has an edge with at most
kother nodes, wherekis given. - The sum of the weights of the remaining edges is maximized.
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:
- Node 2 has edges with 3 other nodes. We remove the edge
[0, 2, 2], ensuring that no node has edges with more thank = 2nodes. - The sum of weights is 22, and we can't achieve a greater sum. Thus, the answer is 22.
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:
- Since no node has edges connecting it to more than
k = 3nodes, we don't remove any edges. - The sum of weights is 65. Thus, the answer is 65.
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] <= 106- The input is generated such that
edgesform a valid tree.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores every possible subset of edges. For each subset, it checks if the degree constraint (each node connected to at most k other nodes) is satisfied for all nodes. If the constraint holds, the sum of weights of the edges in the subset is calculated and compared with the maximum sum found so far. This exhaustive search is implemented using recursion with backtracking.
Algorithm
- Define a recursive function
backtrack(edgeIndex, currentWeight, degrees). - The base case for the recursion is when
edgeIndexreaches the total number of edges. In the base case, check if thedegreesarray for all nodes satisfies the constraint (degree <= k). If it does, update the global maximum weight. If not, this path is invalid. - In the recursive step, for the edge at
edgeIndex, explore two branches:- Exclude the edge: Make a recursive call
backtrack(edgeIndex + 1, currentWeight, degrees). - Include the edge: Add its weight to
currentWeight, increment the degrees of its two endpoint nodes, and then make a recursive callbacktrack(edgeIndex + 1, newWeight, newDegrees). Remember to backtrack by undoing the changes todegreesafter the call returns.
- Exclude the edge: Make a recursive call
- Initialize the process by calling
backtrack(0, 0, new int[n]).
Walkthrough
The brute-force method systematically generates all 2^(n-1) subsets of edges. For each subset, we form a graph and verify if the degree of every node is at most k. If this condition is met, we compute the sum of weights of the edges in the current subset and update our answer with the maximum sum found.
This can be implemented with a recursive backtracking function. The function would iterate through each edge, making a decision to either include it in our set or exclude it. After considering all edges, we have a complete subset, which we then validate against the degree constraints.
class Solution { long maxWeight = 0; int[][] edges; int n; int k; public long maximumValueSum(int[][] edges, int k) { this.edges = edges; this.n = edges.length + 1; this.k = k; backtrack(0, 0, new int[n]); return maxWeight; } private void backtrack(int edgeIndex, long currentWeight, int[] degrees) { if (edgeIndex == edges.length) { for (int deg : degrees) { if (deg > k) { return; // Invalid configuration } } maxWeight = Math.max(maxWeight, currentWeight); return; } int u = edges[edgeIndex][0]; int v = edges[edgeIndex][1]; int weight = edges[edgeIndex][2]; // Case 1: Exclude the current edge backtrack(edgeIndex + 1, currentWeight, degrees); // Case 2: Include the current edge degrees[u]++; degrees[v]++; backtrack(edgeIndex + 1, currentWeight + weight, degrees); degrees[u]--; // backtrack degrees[v]--; // backtrack }}Complexity
Time
O(2^N * N). There are `n-1` edges, leading to `2^(n-1)` subsets. For each subset, we validate the degrees of `N` nodes, taking `O(N)` time.
Space
O(N) for the recursion stack depth and the `degrees` array.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
Solutions
Solution
class Solution {private List<int[]>[] g;private int k;public long maximizeSumOfWeights(int[][] edges, int k) { this.k = k; int n = edges.length + 1; g = new List[n]; Arrays.setAll(g, i->new ArrayList<>()); for (var e : edges) { int u = e[0], v = e[1], w = e[2]; g[u].add(new int[]{v, w}); g[v].add(new int[]{u, w}); } var ans = dfs(0, -1); return Math.max(ans[0], ans[1]); }private long[] dfs(int u, int fa) { long s = 0; List<Long> t = new ArrayList<>(); for (var e : g[u]) { int v = e[0], w = e[1]; if (v == fa) { continue; } var res = dfs(v, u); s += res[0]; long d = w + res[1] - res[0]; if (d > 0) { t.add(d); } } t.sort(Comparator.reverseOrder()); for (int i = 0; i < Math.min(t.size(), k - 1); ++i) { s += t.get(i); } return new long[]{s + (t.size() >= k ? t.get(k - 1) : 0), s}; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.