3367. Maximize Sum of Weights after Edge Removals
Asked at Uber, LinkedIn
Difficulty
Hard
Time
O(n * k)
Space
O(n * k)
Pattern
Dynamic Programming
Companies
2
Problem
You are given an undirected tree with n nodes numbered 0 to n - 1. Each edge has a positive integer weight. You may delete zero or more edges, but after deleting, every node must keep edges to at most k other nodes (its degree must be at most k).
Your goal is to keep the total weight of the remaining edges as large as possible. Return that maximum possible total weight.
Note that deleting an edge lowers the degree of both of its endpoints by one. So the constraint is a degree limit on every node at the same time. You do not have to delete exactly k edges — you delete as few as needed to satisfy the degree rule while keeping the weight sum maximal.
Degree limit on every node
Constraints
- ●
2 <= n <= 10^5 - ●
1 <= k <= n - 1 - ●
edges.length == n - 1 - ●
edges[i].length == 3 - ●
0 <= edges[i][0] <= n - 1 - ●
0 <= edges[i][1] <= n - 1 - ●
1 <= edges[i][2] <= 10^6 - ●
The input is generated such that edges form a valid tree.
Examples
edges = [[0,1,4],[0,2,2],[2,3,12],[2,4,6]], k = 222edges = [[0,1,5],[1,2,10],[0,3,15],[3,4,20],[3,5,5],[0,6,10]], k = 365Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber questions → |
| Hard | View all LinkedIn questions → |
How to Think About It
Brute force: try all combinations of k edges to remove and compute the score for each — exponential and infeasible.
Think about tree DP where each node tracks the best score for its subtree given how many edges are removed within it.
Root the tree and define dp[u][j] as the maximum score achievable in the subtree of u when j edges are removed in that subtree.
For each child edge (u, v), decide whether to cut it (gain the subtree score of v) or keep it (merge v's DP into u's).
Optimal: run a DFS-based DP with a knapsack-style merge at each node in O(nk²) time using subtree-size pruning.
Optimal Approach
Root the tree at node 0. Define dp[u][j] as the maximum score achievable in the subtree rooted at u when exactly j edges are removed within that subtree. For each child v of u via edge with weight w, we have two choices: cut the edge (contributing dp[v][j] to the result and incrementing the cut count) or keep the edge (merging v DP values into u). We merge children one by one using a knapsack-style inner loop, iterating j in reverse to avoid overwriting. The answer is dp[0][k]. Subtree-size pruning limits the inner loop and keeps the complexity at O(nk^2).
Tree DP: keep the best k child edges
What Trips People Up in Real Interviews
Clarify what the score of a component is — is it the sum of all edge weights, or the maximum spanning tree weight?
Root the tree arbitrarily (e.g., at node 0) and think top-down before coding.
When merging child DP arrays into the parent, iterate in reverse to avoid overwriting values (knapsack pattern).
Prune by subtree size: the number of removable edges in a subtree cannot exceed its size minus one.
Watch out for integer overflow when edge weights or n are large — use long in Java/C++.
Solution Code
O(n * k) timeimport sys
sys.setrecursionlimit(300000)
def maximizeSumOfWeights(n, edges, k):
from collections import defaultdict
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
size = [0] * n
dp = [[0] * (k + 1) for _ in range(n)]
def dfs(u, parent):
size[u] = 1
for v, w in graph[u]:
if v == parent:
continue
dfs(v, u)
new_dp = dp[u][:]
for j in range(min(k, size[u] - 1), -1, -1):
forjj in range(min(k - j, size[v] - 1), -1, -1):
val = dp[v][jj] + (w if jj == size[v] - 1 else 0)
if jj + 1 <= k:
new_dp[j + jj + 1] = max(new_dp[j + jj + 1], dp[u][j] + val)
new_dp[j + jj] = max(new_dp[j + jj], dp[u][j] + dp[v][jj])
dp[u] = new_dp
size[u] += size[v]
dfs(0, -1)
return max(dp[0])Frequently Asked Questions
What is the Maximize Sum of Weights after Edge Removals problem?
Given a weighted tree with n nodes, you are allowed to remove exactly k edges. After removal the tree breaks into k+1 connected components. The score is the sum of maximum-weight-edge-in-cycle-free-subgraph for each component. The goal is to maximize the total score by choosing which k edges to remove.
How do you solve Maximize Sum of Weights after Edge Removals?
The optimal approach runs in O(n * k) time and O(n * k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Maximize Sum of Weights after Edge Removals?
Maximize Sum of Weights after Edge Removals is asked at Uber, LinkedIn. It is a hard difficulty problem.
What are common mistakes on Maximize Sum of Weights after Edge Removals?
- Clarify what the score of a component is — is it the sum of all edge weights, or the maximum spanning tree weight?
- Root the tree arbitrarily (e.g., at node 0) and think top-down before coding.
- When merging child DP arrays into the parent, iterate in reverse to avoid overwriting values (knapsack pattern).
- Prune by subtree size: the number of removable edges in a subtree cannot exceed its size minus one.
- Watch out for integer overflow when edge weights or n are large — use long in Java/C++.