Maximize Sum of Weights after Edge Removals
Asked at Uber
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | HARD | View all Uber 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).
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
import 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximize Sum of Weights after Edge Removals?
Maximize Sum of Weights after Edge Removals is asked at Uber. 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++.