Show problems as
Classic problem #3367HardDynamic ProgrammingTreeDepth-First SearchSorting

Maximize Sum of Weights after Edge Removals

Real-world version: Capping Links at Every Fibre Hub
Tracked in this browser only
Read Maximize Sum of Weights after Edge Removals on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A fibre network is described by links. There are links.length + 1 hubs, numbered from 0, and each entry links[i] = [a, b, w] is a two-way fibre run between hub a and hub b carrying w gigabits. The runs form a tree: every hub reaches every other hub along exactly one chain of runs.

The switches being installed are small, so a hub can terminate at most ports of the runs that touch it. Any run not terminated at both of its hubs has to be pulled out.

Decide which runs to pull out so that every hub ends up touched by at most ports of the remaining runs, and return the largest total gigabits the remaining runs can carry.

Examples

Example 1

Input
links = [[0, 1, 5], [0, 2, 3], [0, 3, 4]], ports = 1
Output
5

All three runs touch hub 0, which may terminate only one of them. Keeping the run to hub 1 leaves every hub touched by at most one run, for a total of 5 gigabits.

Example 2

Input
links = [[0, 1, 3], [1, 2, 5], [2, 3, 3]], ports = 1
Output
6

Keeping the runs [0, 1] and [2, 3] touches each of the four hubs exactly once, which is within the single port every hub has, and carries 6 gigabits.

Example 3

Input
links = [[0, 1, 4], [1, 2, 6], [2, 3, 4]], ports = 3
Output
14

No hub here touches more than two runs, so with three ports each nothing has to be pulled out and the total is 14 gigabits.

Constraints

  • n == links.length + 1
  • 2 <= n <= 10^5
  • 1 <= ports <= n - 1
  • links[i].length == 3
  • 0 <= links[i][0], links[i][1] <= n - 1
  • 1 <= links[i][2] <= 10^6
  • The runs form a tree over the n hubs.
  • The answer is at most (n - 1) * 10^6, so it stays below 10^11.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_kept_bandwidth(links: list[list[int]], ports: int) -> int:
Java
public long maxKeptBandwidth(int[][] links, int ports)

More on the same topics