Sum of Distances in Tree

Given an undirected tree with n nodes labeled from 0 to n-1, return an array where answer[i] is the sum of distances from node i to every other node. This is a classic rerooting problem because the solution first computes subtree information and then reuses it while changing the root.

Input Format

n and edges describe a tree

Output Format

sum of distances for every node

Constraints

  • 1 <= n <= 10^5
  • edges.length = n-1
  • The edges array describes an undirected tree.

Examples

Example 1:

Input:

n = 6
edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]

Output:

[8,12,6,10,10,10]

Explanation:

This is the standard rerooting example: node 2 is central, and the sums spread outward accordingly.

Example 2:

Input:

n = 4
edges = [[0,1],[1,2],[1,3]]

Output:

[5,3,5,5]

Explanation:

Node 1 is closest to all others, so it has the smallest total distance.

Loading...
Sum of Distances in Tree - Advanced Trees