Cutting the parcel spur

A courier network is being handed to two contractors, and the planner may sever exactly one link to divide it. There are n - 1 links, and you do not have time to weigh both halves of each one separately.

The problem

A route map hangs off a single depot. Every sorting stop takes parcels of its own and feeds at most two onward spurs, so the map is a binary tree with the depot at the root. Stop i handles parcels[i] parcels a day.

Severing one link splits the map into two pieces, each still connected: the part hanging below the cut, and everything else. The planner scores a cut by multiplying the daily parcel totals of the two pieces, because that product is largest when the two contractors get the most even share. Find the highest score any single cut can reach, and report it modulo 10**9 + 7.

The map arrives level by level, with None where a stop has no spur in that slot: [4, 2, 9, 3, 5, None, 7] is a depot of 4 feeding stops 2 and 9, where 2 feeds 3 and 5, and 9 feeds only 7.

Input. network — the map in level-order form, integers and None.

Output. The largest product of the two pieces' parcel totals, modulo 10**9 + 7.

Example.

network = [4, 2, 9, 3, 5, None, 7]   ->  224

The whole map handles 30 parcels. Cutting the link above stop 9 leaves 9 + 7 = 16 below it and 14 above: 16 · 14 = 224. Cutting above stop 2 splits the stops three and three, which looks fairer, but the totals are 10 and 20 — only 200.

A second example, a map with no branching at all:

network = [8, 1, None, 6, None, None, 2]   ->  72

The stops form one chain, 8 → 1 → 6 → 2, totalling 17. Cutting below the depot gives 9 and 8, and cutting below stop 1 gives 8 and 9: two different links tie at 72. Cutting the last link gives 2 and 15, worth 30.

Constraints.

• 2 <= number of stops <= 5 * 10^4
• 1 <= parcels at a stop <= 10^4
• The map may be a single chain 50,000 stops deep.

Hints

Approach

Brute force

Take each of the n - 1 links in turn, walk both pieces and add up their parcels. Each cut costs O(n), so the total is O(n²) — around 2.5 billion additions on a 50,000-stop map.

The insight

A cut is named by the stop below it, and the piece it detaches is exactly that stop's subtree — so the whole answer is one sweep of subtree totals.

A tree has no second route between two stops, so removing one link cannot leave three pieces or reconnect anything: the side without the depot is precisely what hangs below the cut. Call that below[stop]; the other side is total - below[stop], with no second walk. And below[stop] is parcels[stop] + below[left] + below[right], so children first, parent after — one post-order pass fills every entry.

Algorithm

1. Rebuild the stops from the level-order list.
2. Flatten the map into a list, parents before children, using an explicit stack.
3. Walk that list backwards, setting below[stop] from the stop's own parcels plus its children's totals. total is below[depot].
4. For every stop except the depot, score below[stop] * (total - below[stop]) and keep the largest as an ordinary integer.
5. Reduce that maximum modulo 10**9 + 7 once, at the end.

Complexity

Time O(n) — one pass to flatten, one to total, one to score. Space O(n) for the stack and the per-stop totals.

Pitfalls

• Reducing before comparing. With three stops of 50,000 the best cut scores 5,000,000,000, which is 999,999,972 after reduction — smaller than plenty of worse cuts. Compare exact products; reduce the winner once.
• Recursing on the map. A chain 50,000 stops deep raises RecursionError long before it returns, since Python stops at about 1,000 frames. Flatten with a stack instead.
• Scoring the depot's own link. The depot has nothing above it, so total * 0 is not a real cut; counting it is harmless only because the product is zero, and it hides the case where every real cut is worse.
• Judging balance by stop count. In the first example the three-and-three split scores 200 and the two-and-four split scores 224. Parcels decide, not stops.

Solution

"""Cutting the parcel spur — subtree totals in one post-order sweep, then one pass over the cuts."""

from collections import deque

MOD = 10**9 + 7


class Stop:
    """One sorting stop: its own parcel count and up to two onward spurs."""

    __slots__ = ("parcels", "left", "right")

    def __init__(self, parcels):
        self.parcels = parcels
        self.left = None
        self.right = None


def build(level_order):
    """Rebuild the network from its compact level-order form."""
    if not level_order or level_order[0] is None:
        return None
    root = Stop(level_order[0])
    queue = deque([root])
    i = 1
    while queue and i < len(level_order):
        # invariant: only real stops are queued, so a gap never claims a spur slot
        stop = queue.popleft()
        for slot in ("left", "right"):
            if i >= len(level_order):
                break
            value = level_order[i]
            i += 1
            if value is not None:
                child = Stop(value)
                setattr(stop, slot, child)
                queue.append(child)
    return root


def solve(network):
    root = build(network)
    if root is None:
        return 0

    # Flatten first so the sweep costs no recursion depth on a long single spur.
    order, stack = [], [root]
    while stack:
        stop = stack.pop()
        order.append(stop)
        if stop.left:
            stack.append(stop.left)
        if stop.right:
            stack.append(stop.right)

    # Children come after their parent in `order`, so walking it backwards
    # guarantees both subtree totals are known before the parent is summed.
    below = {}
    for stop in reversed(order):
        below[id(stop)] = (
            stop.parcels
            + below.get(id(stop.left), 0)
            + below.get(id(stop.right), 0)
        )

    total = below[id(root)]
    best = 0
    for stop in order:
        if stop is root:
            continue          # the link above the depot is not a cut we may make
        low = below[id(stop)]
        # Compare true products, never products already reduced mod 10**9 + 7.
        best = max(best, low * (total - low))
    return best % MOD

TESTS = [
    (([4, 2, 9, 3, 5, None, 7],), 224),
    (([8, 1, None, 6, None, None, 2],), 72),
    (([3, 1, None, None, 4],), 16),
    (([10, 10],), 100),
    (([1, 2, 3, 4, 5, 6, 7],), 192),
    (([50000] * 3,), 999999972),
    (([],), 0),
]

Variants

• The lantern wire — also a question of where to split, but the pieces there interact, so one sweep is not enough.
• The fly cue sheet — DP over a grid, where the state is a whole row rather than a single stop.