Description
Given a tree of n nodes, return an array where ans[i] is the sum of distances between node i and all other nodes.
Examples
Input:
n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]Output:
[8,12,6,10,10,10]Explanation:
Distance sums.
Input:
n = 6, edges = [[1]]Output:
[1]Explanation:
Minimal case with a single-element matrix.
Input:
n = 4, edges = [[0,1],[1,2],[2,3]]Output:
[6,4,4,6]Explanation:
In this linear tree (path graph), distance sums are [6, 4, 4, 6]. End nodes have the largest sums.
Constraints
- •
1 ≤ n ≤ 3 × 10⁴