Maximize Sum of Weights after Edge Removals

Maximize Sum of Weights after Edge Removals - Problem

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] = [u_i, v_i, w_i] indicates that there is an edge between nodes u_i and v_i with weight w_i in the tree.

Your task is to remove zero or more edges such that:

Each node has an edge with at most k other nodes, where k is 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.

Input & Output

Example 1 — Basic Tree with k=2

$ Input: edges = [[0,1,4],[1,2,2],[1,3,3]], k = 2

› Output: 9

💡 Note: Node 1 can connect to at most 2 nodes. We keep edges [0,1,4] and [1,3,3] for maximum weight 4+3=7. But optimal solution keeps [1,2,2] and [1,3,3] for weight 2+3=5, plus we can also keep other edges. Actually, we can keep all edges since each node has degree ≤ 2, giving total weight 4+2+3=9.

Example 2 — Degree Constraint Forces Removal

$ Input: edges = [[0,1,1],[1,2,2],[1,3,3],[1,4,4]], k = 2

› Output: 7

💡 Note: Node 1 connects to 4 other nodes but can only keep 2 connections. To maximize weight, keep the two highest weight edges: [1,4,4] and [1,3,3] for total weight 4+3=7.

Example 3 — Single Edge

$ Input: edges = [[0,1,10]], k = 1

› Output: 10

💡 Note: Only one edge exists and both nodes have degree 1 ≤ k=1, so keep the edge with weight 10.

Constraints

1 ≤ n ≤ 10⁴
0 ≤ edges.length ≤ min(n × (n - 1) / 2, 10⁴)
edges[i].length == 3
0 ≤ u_i < v_i < n
1 ≤ w_i ≤ 10⁶
1 ≤ k ≤ n - 1

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Undirected tree with weighted edges and degree limit k

Apply Constraints

Each node can connect to at most k other nodes

Maximize Weight

Select subset of edges with maximum total weight

Key Takeaway

🎯 Key Insight: Use tree DP to optimally select the best k edges for each node while considering parent connections

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The optimal approach uses tree DP with DFS traversal to select the best k edges for each node while considering parent connections. The key insight is that for each node, we can keep at most k edges total, and if we connect to our parent, we can only keep k-1 child edges. Time complexity: O(n log n), Space complexity: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Edge Selection	O(n log n)	O(n)	Sort all edges by weight and greedily select edges while maintaining degree constraints
Brute Force - Try All Combinations	O(2^n × n)	O(n)	Generate all possible subsets of edges and check which valid subset has maximum weight
Tree DP with DFS	O(n log n)	O(n)	Use tree DP to track best k edges for each subtree considering parent connection

Greedy Edge Selection — Algorithm Steps

Sort all edges by weight in descending order
For each edge, check if both endpoints have degree < k
If valid, add edge to result and increment degrees

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Edges

Sort all edges by weight in descending order

Check Degrees

For each edge, verify both endpoints have degree < k

Add Valid Edges

Include edge if both nodes can accept it

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Edge {
    int u, v, w;
};

int compare(const void* a, const void* b) {
    struct Edge* ea = (struct Edge*)a;
    struct Edge* eb = (struct Edge*)b;
    return eb->w - ea->w; // Descending order
}

long long solution(int edges[][3], int edgeCount, int k) {
    if (edgeCount == 0) return 0;
    
    int n = edgeCount + 1;
    int degree[1000] = {0};
    
    // Convert to struct array for sorting
    struct Edge edgeArray[1000];
    for (int i = 0; i < edgeCount; i++) {
        edgeArray[i].u = edges[i][0];
        edgeArray[i].v = edges[i][1];
        edgeArray[i].w = edges[i][2];
    }
    
    qsort(edgeArray, edgeCount, sizeof(struct Edge), compare);
    
    long long totalWeight = 0;
    
    for (int i = 0; i < edgeCount; i++) {
        int u = edgeArray[i].u, v = edgeArray[i].v, w = edgeArray[i].w;
        if (degree[u] < k && degree[v] < k) {
            degree[u]++;
            degree[v]++;
            totalWeight += w;
        }
    }
    
    return totalWeight;
}

int main() {
    int edges[1000][3];
    int edgeCount = 0;
    int k;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for edges
    char *ptr = line + 1; // Skip [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgeCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            edges[edgeCount][1] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            edges[edgeCount][2] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            edgeCount++;
        }
        ptr++;
    }
    
    scanf("%d", &k);
    
    printf("%lld\n", solution(edges, edgeCount, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting edges by weight takes O(n log n), then O(n) to process each edge

⚡ Linearithmic

Space Complexity

O(n)

Store degree array for n nodes plus sorted edge list

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

248 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Edge Selection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler