0675HardDynamic ProgrammingTreeDepth-First SearchGraph TheoryDP on Trees

Total Doorways from Every Gallery

Tracked in this browser only

Trains the technique from

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 museum has n galleries numbered 0 to n - 1, joined by n - 1 doorways. The doorways arrive as an edge list: doorways[i] = [a, b] says a doorway joins gallery a and gallery b, and it can be walked in either direction. Every gallery can be reached from every other, and with only n - 1 doorways there is exactly one route between any two galleries that never uses the same doorway twice.

The cost of walking between two galleries is the number of doorways on that route, and the cost from a gallery to itself is 0.

Return one total per gallery, in gallery order: position i of the returned list holds the sum of the walking costs from gallery i to all n galleries.

Examples

Example 1

Input: n = 7, doorways = [[0, 1], [1, 2], [1, 3], [0, 4], [4, 5], [4, 6]]
Output: [10, 11, 16, 16, 11, 16, 16]

From gallery `0` the costs are 0 to itself, 1 to galleries `1` and `4`, and 2 to galleries `2`, `3`, `5` and `6`, which comes to 10. From gallery `2` the costs are 1 to `1`, 2 to `0` and `3`, 3 to `4`, and 4 to `5` and `6`, which comes to 16.

Example 2

Input: n = 6, doorways = [[5, 4], [4, 3], [3, 2], [2, 1], [1, 0]]
Output: [15, 11, 9, 9, 11, 15]

The galleries form a single corridor. From the gallery at one end the costs run 0, 1, 2, 3, 4, 5 and add up to 15, while from a gallery in the middle the costs are smaller.

Example 3

Input: n = 5, doorways = [[2, 0], [2, 1], [2, 3], [2, 4]]
Output: [7, 7, 4, 7, 7]

Gallery `2` has a doorway to each of the other four, so its total is 4. Any other gallery pays 1 to reach gallery `2` and 2 to reach each of the remaining three, a total of 7.

Constraints

1 <= n <= 3 * 10^4
doorways.length == n - 1
doorways[i].length == 2
0 <= a, b < n
a != b
The doorways join the galleries as described above.

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 total_hops(n: int, doorways: list[list[int]]) -> list[int]:

Java

public int[] totalHops(int n, int[][] doorways)

The intended approach

Time O(n): the doorway lists hold 2(n - 1) entries and each of the three sweeps visits every gallery once.Space O(n) for the doorway lists, the walk order and the two tables.

Build the doorway lists, then order the galleries by an explicit-stack walk from gallery `0`, recording the gallery each one was first reached from. Sweeping that order backwards gives, for every gallery, how many galleries sit at or below it and the total cost of reaching them, since a gallery's own total is the sum of its children's totals plus one extra doorway for each gallery below it. Sweeping the order forwards then converts a gallery's total from its parent's: moving one step down shortens the walk to the galleries at or below that gallery by one each and lengthens the walk to all the others by one each, so the change is the gallery count minus twice the number of galleries at or below it.

Pythonentry point: total_hops

def total_hops(n, doorways):
    # O(n) two-pass reroot, driven by an explicit stack so a long chain cannot overflow
    adj = [[] for _ in range(n)]
    for a, b in doorways:
        adj[a].append(b)
        adj[b].append(a)
    above = [-1] * n
    order = []
    reached = [False] * n
    stack = [0]
    reached[0] = True
    while stack:
        node = stack.pop()
        order.append(node)
        for nxt in adj[node]:
            if not reached[nxt]:
                reached[nxt] = True
                above[nxt] = node
                stack.append(nxt)
    below = [1] * n
    total = [0] * n
    for node in reversed(order):
        up = above[node]
        if up != -1:
            below[up] += below[node]
            total[up] += total[node] + below[node]
    for node in order:
        up = above[node]
        if up != -1:
            total[node] = total[up] + n - 2 * below[node]
    return total

The obvious version

For each gallery in turn, spread outwards level by level from it, giving every gallery a cost one greater than the gallery it was reached from, and add up the costs. Repeat for all n starting galleries.

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_total_hops(n, doorways):
    adj = [[] for _ in range(n)]
    for a, b in doorways:
        adj[a].append(b)
        adj[b].append(a)
    answer = []
    for start in range(n):
        dist = [-1] * n
        dist[start] = 0
        queue = [start]
        head = 0
        while head < len(queue):
            node = queue[head]
            head += 1
            for nxt in adj[node]:
                if dist[nxt] == -1:
                    dist[nxt] = dist[node] + 1
                    queue.append(nxt)
        answer.append(sum(dist))
    return answer

How this problem was checked

Reference solution executed against 8 test cases — 8 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