Weighted Tree: Total Distance from Each Node to All Other Nodes
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
An undirected tree has `n` nodes labeled `0` to `n - 1`, and every edge has a positive integer weight. The distance between two nodes is the sum of the edge weights on the unique path that joins them. Write a function that returns, for every node, the sum of its distances to all the other nodes.
### Function Signature
```python
def weighted_distance_sums(n: int, edges: list[list[int]]) -> list[int]:
```
### Rules
- `edges[i] = [u, v, w]` is an undirected edge of weight `w` between nodes `u` and `v`. `[u, v, w]` and `[v, u, w]` describe the same edge, and each edge is listed exactly once.
- The edges always form one tree: there are exactly `n - 1` of them, and every pair of nodes is joined by exactly one path.
- Return a list `answer` of length `n` in which `answer[i]` is the sum, over every node `j` other than `i`, of the distance between `i` and `j`. The list is indexed by node label, so the answer is unique.
- When `n = 1` there are no edges, and the answer is `[0]`.
### Constraints
- `1 <= n <= 3 * 10^4`
- `len(edges) == n - 1`
- `0 <= u, v <= n - 1` and `u != v` for every edge
- `1 <= w <= 10^4` for every edge
- `edges` is in no particular order.
- A single `answer[i]` can reach about `4.5 * 10^12`, which exceeds `2^31 - 1`: use 64-bit integers in a language with fixed-width integers. Every value stays below `2^53`.
### Examples
**Example 1**
```text
Input: n = 6, edges = [[0, 1, 2], [0, 2, 1], [2, 3, 3], [2, 4, 1], [2, 5, 2]]
Output: [12, 20, 10, 22, 14, 18]
```
From node `0`, the distances to nodes `1`, `2`, `3`, `4` and `5` are `2`, `1`, `4`, `2` and `3`, which sum to `12`. From node `3`, the distances to nodes `0`, `1`, `2`, `4` and `5` are `4`, `6`, `3`, `4` and `5`, which sum to `22`.
**Example 2**
```text
Input: n = 3, edges = [[1, 0, 5], [2, 1, 1]]
Output: [11, 6, 7]
```
The tree is the path `0 - 1 - 2`. Node `0` is at distance `5` from node `1` and `6` from node `2`; node `1` is at distance `5` from node `0` and `1` from node `2`; node `2` is at distance `6` from node `0` and `1` from node `1`.
**Example 3**
```text
Input: n = 1, edges = []
Output: [0]
```
A single node has no other nodes to reach.
Overview: Given an undirected tree whose edges carry positive integer weights, return for every node the sum of its weighted distances to all other nodes. The problem tests tree traversal, subtree aggregation and producing all n answers fast enough for trees with tens of thousands of nodes, with sums that need 64-bit integers.