Maximize Sum of Weights after Edge Removals

Maximize Sum of Weights after Edge Removals

What is this problem about?

In this problem, you are given an undirected tree with weighted edges. You are also given an integer k. You must remove some edges such that every node in the resulting graph has a degree (number of connected edges) of at most k. Your objective is to find a valid configuration of edge removals that maximizes the sum of the weights of the remaining edges.

Why is this asked in interviews?

This is a Hard-level Graph/Tree DP question. It tests a candidate's ability to perform Dynamic Programming on Trees. Interviewers ask it to evaluate if you can define states based on a parent-child relationship. Specifically, you must calculate the optimal score for a subtree if the edge to its parent is kept, versus if the edge to its parent is removed.

Algorithmic pattern used

This problem leverages Depth-First Search (DFS) with Tree DP. For every node, the DFS returns two values: [keep_parent_edge, remove_parent_edge]. Inside the DFS for node u:

1. Recursively call DFS for all children of u.
2. For each child v, you evaluate the "gain" of keeping the edge u-v vs removing it. The gain is weight(u, v) + dfs(v)[keep] - dfs(v)[remove].
3. To maximize the score, you want to keep the edges with the highest positive gains, but node u can only keep at most k edges (or k-1 if we assume the parent edge is kept).
4. You sort the gains descending and pick the top k or k-1 to form your DP return states.

Example explanation

Let k = 1. A node can only have 1 edge. Node A is connected to B (weight 10) and C (weight 5). DFS at A:

• A must choose at most 1 edge.
• Gain of keeping A-B is 10. Gain of keeping A-C is 5.
• Since $k=1$, A chooses to keep A-B. The sum is 10. A-C is removed. If A had a parent P, we must return two states to P:

1. remove_parent_edge: A can use its 1 allowance to keep A-B. Returns 10.
2. keep_parent_edge: A's 1 allowance is consumed by the A-P edge! A must drop both B and C. Returns 0. Parent P will use these two values (10 and 0) to decide if keeping the P-A edge is worth the cost of forcing A to drop B.

Common mistakes candidates make

The most frequent mistake is using a greedy approach: just sorting all edges globally by weight and picking them until degrees hit k. This global greedy approach fails on trees because an edge might be skipped globally, but it was the only edge for a specific leaf, breaking the optimal local substructure. You MUST use post-order Tree DP to evaluate the cascading costs of removals.

Interview preparation tip

To excel at the Maximize Sum of Weights after Edge Removals interview question, practice returning arrays of states from DFS functions. The state [score_if_parent_edge_kept, score_if_parent_edge_removed] is a universal template for tree-edge constraints. If you sort the "deltas" (the difference between keeping and removing a child) inside the node, you can greedily pick the best children without violating the degree limit k.