0528HardDynamic ProgrammingTreeDepth-First SearchSorting

Capping Links at Every Fibre Hub

Tracked in this browser only

Trains the technique from

LeetCode 3367Maximize Sum of Weights after Edge Removals

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_kept_bandwidth(links: list[list[int]], ports: int) -> int:

Java

public long maxKeptBandwidth(int[][] links, int ports)

The intended approach

Time O(n log n): each hub sorts the gains its children offer, and every run is looked at a constant number of times.Space O(n) for the adjacency lists, the two totals per hub and the stack.

Hang the tree from hub 0 and work upward, keeping two totals per hub: the best its subtree can carry when the run up to its parent is pulled out, and the best when that run stays, which costs the hub one of its ports. A hub starts from the sum of its children's dropped-run totals, and keeping the run down to a child changes that total by a fixed amount, so each child offers one gain figure. Sorting the positive gains and adding the best `ports` of them, or the best `ports - 1` when a port is already spoken for, gives both totals. The walk order comes from an explicit stack, so a chain of a hundred thousand hubs is safe.

Pythonentry point: max_kept_bandwidth

def max_kept_bandwidth(links, ports):
    # O(n log n): one post-order pass over the tree from an explicit stack, each
    # hub sorting the gains offered by its children.
    n = len(links) + 1
    near = [[] for _ in range(n)]
    for link in links:
        a, b, w = link[0], link[1], link[2]
        near[a].append((b, w))
        near[b].append((a, w))
    owner = [-1] * n
    up_weight = [0] * n
    order = []
    seen = [False] * n
    seen[0] = True
    stack = [0]
    while stack:
        here = stack.pop()
        order.append(here)
        for there, w in near[here]:
            if not seen[there]:
                seen[there] = True
                owner[there] = here
                up_weight[there] = w
                stack.append(there)
    free = [0] * n   # best for this subtree with the link to the parent dropped
    tied = [0] * n   # best for this subtree with the link to the parent kept
    for i in range(len(order) - 1, -1, -1):
        here = order[i]
        base = 0
        gains = []
        for there, w in near[here]:
            if owner[there] == here:
                base += free[there]
                gain = tied[there] + w - free[there]
                if gain > 0:
                    gains.append(gain)
        gains.sort(reverse=True)
        free[here] = base + sum(gains[:ports])
        tied[here] = base + sum(gains[:ports - 1])
    return free[0]

The obvious version

Enumerate every subset of the runs, count how many kept runs touch each hub, discard any subset that overloads a hub and keep the largest total.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_kept_bandwidth(links, ports):
    n = len(links) + 1
    total = len(links)
    best = 0
    for mask in range(1 << total):
        degree = [0] * n
        gross = 0
        ok = True
        for i in range(total):
            if mask >> i & 1:
                a, b, w = links[i][0], links[i][1], links[i][2]
                degree[a] += 1
                degree[b] += 1
                if degree[a] > ports or degree[b] > ports:
                    ok = False
                    break
                gross += w
        if ok and gross > best:
            best = gross
    return best

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in