Tap here to switch tabs
Problem
Submissions

Problem: Maximize Sum of Weights after Edge Removals

Try to solve the Maximize Sum of Weights after Edge Removals problem.

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

Try to solve the Maximize Sum of Weights after Edge Removals problem.

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.