Tap here to switch tabs
Problem
Submissions

Problem: Maximize Sum of Weights after Edge Removals

Maximize Sum of Weights after Edge Removals asks you to remove tree edges so every node has at most k neighbors, while maximizing the total weight of the edges that remain.

Statement

There is an undirected tree with nn nodes numbered from 00 to n−1n - 1. You are given a 2D2 {D} integer array edges of length n−1n - 1, where edges[i] =[ui,vi,wi]= [u_i, v_i, w_i] denotes an edge connecting nodes uiu_i and viv_i with weight wiw_i. You are also given an integer k.

You may remove any number of edges from the tree such that in the resulting graph, every node is connected to at most k other nodes.

Return the maximum possible total sum of edge weights of the remaining edges.

Constraints:

  • 2≤n≤1052 \leq n \leq 10^5

  • 1≤1 \leq k ≤n−1\leq n - 1

  • edges.length =n−1= n - 1

  • edges[i].length =3= 3

  • 0≤0 \leq edges[i][0] ≤n−1\leq n - 1

  • 0≤0 \leq edges[i][1] ≤n−1\leq n - 1

  • 1≤1 \leq edges[i][2] ≤106\leq 10^6

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximize Sum of Weights after Edge Removals

Maximize Sum of Weights after Edge Removals asks you to remove tree edges so every node has at most k neighbors, while maximizing the total weight of the edges that remain.

Statement

There is an undirected tree with nn nodes numbered from 00 to n−1n - 1. You are given a 2D2 {D} integer array edges of length n−1n - 1, where edges[i] =[ui,vi,wi]= [u_i, v_i, w_i] denotes an edge connecting nodes uiu_i and viv_i with weight wiw_i. You are also given an integer k.

You may remove any number of edges from the tree such that in the resulting graph, every node is connected to at most k other nodes.

Return the maximum possible total sum of edge weights of the remaining edges.

Constraints:

  • 2≤n≤1052 \leq n \leq 10^5

  • 1≤1 \leq k ≤n−1\leq n - 1

  • edges.length =n−1= n - 1

  • edges[i].length =3= 3

  • 0≤0 \leq edges[i][0] ≤n−1\leq n - 1

  • 0≤0 \leq edges[i][1] ≤n−1\leq n - 1

  • 1≤1 \leq edges[i][2] ≤106\leq 10^6

  • The input is generated such that edges represents a valid tree.