545. Total Distance From Each
A delivery company runs n depots numbered 0 to n - 1, joined by n - 1 two-way roads listed in edges, where edges[i] = [u, v] connects depots u and v. Every depot can reach every other depot, and there is exactly one route between any two of them.
For each depot i, compute the sum of the route lengths (counted in roads) from depot i to every other depot. Return an array answer of length n where answer[i] is that sum for depot i. A tree with a single depot yields [0].
Example 1
- Input:
- n = 5, edges = [[3,0],[0,4],[4,1],[1,2]]
- Output:
- [7,7,10,10,6]
- Explanation:
The towns form the chain 3-0-4-1-2; town 3 is 1, 2, 3 and 4 roads from the others (sum 10) while the middle town 4 gives the smallest total, 6.
Example 2
- Input:
- n = 4, edges = [[2,0],[2,1],[2,3]]
- Output:
- [5,5,3,5]
- Explanation:
Town 2 is adjacent to every other town (sum 3), while each outer town is 1 away from town 2 and 2 away from the other two (sum 5).
Constraints
1 ≤ n ≤ 3 * 104 (so every sum fits in a 32-bit integer)
edges.length == n - 1, 0 ≤ u, v < n
The edges form a tree.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)