965. Sum of Distances in Tree (Rerooting)

Given a tree with n nodes labeled 0..n-1 and an undirected edge list, return an array where the i-th entry is the sum of the distances (number of edges) from node i to every other node. Use the rerooting technique for an O(n) solution. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Array — the sum of distances from each node.

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 per node.

Input: {"n":1,"edges":[]}
Output: [0]
Explanation: Only one node.

Input: {"n":2,"edges":[[0,1]]}
Output: [1,1]
Explanation: Each is distance 1 from the other.

Constraints

• 1<=n<=3*10^4
• edges form a tree

Asked by