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:
Node 0 sum is 1+1+2+2+2=8 (distances to all other nodes). Central nodes have smaller sums.
Input:
n = 2, edges = [[0,1]]Output:
[1,1]Explanation:
With 2 nodes connected by one edge, each node has distance 1 to the other, so distance sums are [1,1].
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⁴