Maximize Sum of Weights after Edge Removals
Maximize Sum of Weights after Edge Removals is a hard dynamic programming problem solved with the tree dp pattern.
The best approach, optimal (tree dp with greedy child choice), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every subset of edges) up.
Problem
You are given an undirected tree with n nodes labeled 0 to n - 1, described by edges, where edges[i] = [u_i, v_i, w_i] is an edge of weight w_i between u_i and v_i. You are also given an integer k.
Remove any number of edges (possibly none) so that every node is touched by at most k remaining edges. Return the largest possible total weight of the edges that remain.
Examples
Example 1
- Input
edges = [[0, 1, 5], [1, 2, 3], [1, 3, 8], [3, 4, 2]], k = 2- Output
15- Why
- Node 1 touches three edges, so one must go. Dropping the lightest one (weight 3) keeps 5 + 8 + 2 = 15.
Example 2
- Input
edges = [[0, 1, 6], [1, 2, 10], [2, 3, 6]], k = 1- Output
12- Why
- Keeping the heaviest edge (10) blocks both others. Keeping the two outer edges gives 6 + 6 = 12.
Example 3
- Input
edges = [[0, 1, 2], [0, 2, 3]], k = 2- Output
5- Why
- No node exceeds degree 2, so nothing is removed.
Constraints
2 <= n <= 10^5, wheren = edges.length + 11 <= k <= n - 1edges[i] = [u_i, v_i, w_i]with0 <= u_i, v_i < nand1 <= w_i <= 10^6- The edges form a tree.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every subset of edges) | O(2^n · n) | O(n) |
| Optimal (tree DP with greedy child choice) | O(n log n) | O(n) |
1Brute force (try every subset of edges)
O(2^n · n)There are 2^(n-1) subsets and each one is checked in O(n).O(n)One degree array.Every edge is either kept or removed. Enumerate all 2^(n-1) subsets with a bitmask, count the degree of every node, and among the subsets where every degree is at most k, keep the largest total weight.
- For mask from 0 to 2^m - 1 (m = number of edges):
- Add up the weights of the edges in mask and count degrees.
- If no degree exceeds k, update the best total.
- Return the best total.
class Solution {
public long maximizeSumOfWeights(int[][] edges, int k) {
int m = edges.length, n = m + 1;
long best = 0;
for (int mask = 0; mask < (1 << m); mask++) {
int[] deg = new int[n];
long sum = 0;
boolean ok = true;
for (int i = 0; i < m && ok; i++) {
if ((mask >> i & 1) == 0) continue;
sum += edges[i][2];
if (++deg[edges[i][0]] > k || ++deg[edges[i][1]] > k) ok = false;
}
if (ok) best = Math.max(best, sum);
}
return best;
}
}class Solution:
def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
m = len(edges)
n = m + 1
best = 0
for mask in range(1 << m):
deg = [0] * n
total = 0
ok = True
for i in range(m):
if not (mask >> i) & 1:
continue
u, v, w = edges[i]
total += w
deg[u] += 1
deg[v] += 1
if deg[u] > k or deg[v] > k:
ok = False
break
if ok:
best = max(best, total)
return bestclass Solution {
public:
long long maximizeSumOfWeights(vector<vector<int>>& edges, int k) {
int m = edges.size(), n = m + 1;
long long best = 0;
for (int mask = 0; mask < (1 << m); mask++) {
vector<int> deg(n, 0);
long long sum = 0;
bool ok = true;
for (int i = 0; i < m && ok; i++) {
if (((mask >> i) & 1) == 0) continue;
sum += edges[i][2];
if (++deg[edges[i][0]] > k || ++deg[edges[i][1]] > k) ok = false;
}
if (ok) best = max(best, sum);
}
return best;
}
};function maximizeSumOfWeights(edges, k) {
const m = edges.length, n = m + 1;
let best = 0;
for (let mask = 0; mask < (1 << m); mask++) {
const deg = new Array(n).fill(0);
let sum = 0, ok = true;
for (let i = 0; i < m && ok; i++) {
if (((mask >> i) & 1) === 0) continue;
sum += edges[i][2];
if (++deg[edges[i][0]] > k || ++deg[edges[i][1]] > k) ok = false;
}
if (ok) best = Math.max(best, sum);
}
return best;
}2Optimal (tree DP with greedy child choice)
O(n log n)Each node sorts the gains of its own children, and the children counts add up to n - 1.O(n)Adjacency lists, the order, and two DP arrays.Root the tree at node 0. For every node u compute full[u], the best total inside u's subtree when u may keep up to k child edges, and part[u], the same when u may keep only k - 1 (its parent edge is kept). Start from the sum of full[c] over all children (every child edge removed). Keeping the edge to child c changes the total by gain = w + part[c] - full[c]. Sort the positive gains in decreasing order: full[u] adds the top k of them and part[u] the top k - 1. The answer is full[0]. An explicit stack order (children before parents) avoids deep recursion on long paths.
- Build adjacency lists with weights.
- Traverse from node 0 with a stack to get a parent array and a visiting order.
- Process nodes in reverse order: base = sum of full[c]; collect gains w + part[c] - full[c] that are positive; sort them descending.
- full[u] = base + top k gains; part[u] = base + top k - 1 gains.
- Return full[0].
class Solution {
public long maximizeSumOfWeights(int[][] edges, int k) {
int n = edges.length + 1;
List<int[]>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) {
adj[e[0]].add(new int[] { e[1], e[2] });
adj[e[1]].add(new int[] { e[0], e[2] });
}
int[] parent = new int[n], order = new int[n];
Arrays.fill(parent, -1);
boolean[] seen = new boolean[n];
int[] stack = new int[n];
int top = 0, cnt = 0;
stack[top++] = 0;
seen[0] = true;
while (top > 0) {
int u = stack[--top];
order[cnt++] = u;
for (int[] e : adj[u]) {
if (!seen[e[0]]) {
seen[e[0]] = true;
parent[e[0]] = u;
stack[top++] = e[0];
}
}
}
long[] full = new long[n], part = new long[n];
for (int idx = n - 1; idx >= 0; idx--) {
int u = order[idx];
long base = 0;
List<Long> gains = new ArrayList<>();
for (int[] e : adj[u]) {
int c = e[0];
if (c == parent[u]) continue;
base += full[c];
long g = e[1] + part[c] - full[c];
if (g > 0) gains.add(g);
}
gains.sort(Collections.reverseOrder());
long sum = base;
part[u] = base;
full[u] = base;
for (int i = 0; i < gains.size() && i < k; i++) {
sum += gains.get(i);
if (i < k - 1) part[u] = sum;
full[u] = sum;
}
}
return full[0];
}
}class Solution:
def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
n = len(edges) + 1
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w))
parent = [-1] * n
seen = [False] * n
seen[0] = True
order = []
stack = [0]
while stack:
u = stack.pop()
order.append(u)
for v, _ in adj[u]:
if not seen[v]:
seen[v] = True
parent[v] = u
stack.append(v)
full = [0] * n
part = [0] * n
for u in reversed(order):
base = 0
gains = []
for c, w in adj[u]:
if c == parent[u]:
continue
base += full[c]
g = w + part[c] - full[c]
if g > 0:
gains.append(g)
gains.sort(reverse=True)
full[u] = base + sum(gains[:k])
part[u] = base + sum(gains[:k - 1])
return full[0]class Solution {
public:
long long maximizeSumOfWeights(vector<vector<int>>& edges, int k) {
int n = edges.size() + 1;
vector<vector<pair<int, int>>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back({e[1], e[2]});
adj[e[1]].push_back({e[0], e[2]});
}
vector<int> parent(n, -1), order, stack = {0};
vector<bool> seen(n, false);
seen[0] = true;
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
order.push_back(u);
for (auto& [v, w] : adj[u]) {
if (!seen[v]) {
seen[v] = true;
parent[v] = u;
stack.push_back(v);
}
}
}
vector<long long> full(n, 0), part(n, 0);
for (int idx = n - 1; idx >= 0; idx--) {
int u = order[idx];
long long base = 0;
vector<long long> gains;
for (auto& [c, w] : adj[u]) {
if (c == parent[u]) continue;
base += full[c];
long long g = w + part[c] - full[c];
if (g > 0) gains.push_back(g);
}
sort(gains.rbegin(), gains.rend());
long long sum = base;
full[u] = part[u] = base;
for (int i = 0; i < (int)gains.size() && i < k; i++) {
sum += gains[i];
if (i < k - 1) part[u] = sum;
full[u] = sum;
}
}
return full[0];
}
};function maximizeSumOfWeights(edges, k) {
const n = edges.length + 1;
const adj = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) {
adj[u].push([v, w]);
adj[v].push([u, w]);
}
const parent = new Array(n).fill(-1);
const seen = new Array(n).fill(false);
seen[0] = true;
const order = [];
const stack = [0];
while (stack.length > 0) {
const u = stack.pop();
order.push(u);
for (const [v] of adj[u]) {
if (!seen[v]) {
seen[v] = true;
parent[v] = u;
stack.push(v);
}
}
}
const full = new Array(n).fill(0), part = new Array(n).fill(0);
for (let idx = n - 1; idx >= 0; idx--) {
const u = order[idx];
let base = 0;
const gains = [];
for (const [c, w] of adj[u]) {
if (c === parent[u]) continue;
base += full[c];
const g = w + part[c] - full[c];
if (g > 0) gains.push(g);
}
gains.sort((a, b) => b - a);
let sum = base;
full[u] = part[u] = base;
for (let i = 0; i < gains.length && i < k; i++) {
sum += gains[i];
if (i < k - 1) part[u] = sum;
full[u] = sum;
}
}
return full[0];
}Edge cases to test
- k = 1: the kept edges must form a matching
- k at least the maximum degree: keep everything
- A star, where only the k heaviest edges survive
- A long path (deep tree): avoid deep recursion
- The total can exceed 2^31 - 1, so use a 64-bit sum
Hints
Hint 1
Root the tree. For each node, the only question is which of its child edges to keep, and whether the edge to its parent is kept too.
Hint 2
Compute two values per node: the best total in its subtree if it may keep up to k child edges, and if it may keep only k - 1 (because the parent edge is kept).
Hint 3
Keeping the edge to child c gains w + best_c(k - 1) - best_c(k). Take the largest positive gains first.
FAQ
What is the best time complexity for Maximize Sum of Weights after Edge Removals?
Optimal (tree DP with greedy child choice) runs in O(n log n) time and O(n) extra space. Each node sorts the gains of its own children, and the children counts add up to n - 1.
Which pattern does Maximize Sum of Weights after Edge Removals use?
It is a dynamic programming problem that uses the tree dp pattern.
Is there a brute force solution for Maximize Sum of Weights after Edge Removals?
Yes. Brute force (try every subset of edges) takes O(2^n · n) time and O(n) space. Every edge is either kept or removed.
Which edge cases should I test for Maximize Sum of Weights after Edge Removals?
k = 1: the kept edges must form a matching; k at least the maximum degree: keep everything; A star, where only the k heaviest edges survive; A long path (deep tree): avoid deep recursion; The total can exceed 2^31 - 1, so use a 64-bit sum.