Show problems as
Classic problem #834HardDynamic ProgrammingTreeDepth-First SearchGraph TheoryDP on Trees

Sum of Distances in Tree

Real-world version: Total Doorways from Every Gallery
Tracked in this browser only
Read Sum of Distances in Tree on LeetCode(opens in a new tab)

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

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

Python
def total_hops(n: int, doorways: list[list[int]]) -> list[int]:
Java
public int[] totalHops(int n, int[][] doorways)

More on the same topics