#834

Sum of Distances in Tree

expert · 1065 · lc hard +32 · verified · 65.5% accepted · 5,947 likes · top 70%

Description

Consider an undirected connected tree with n nodes labeled 0 through n - 1 and n - 1 edges.

You are given the integer n and the array edges where edges[i] = [ai, bi] denotes an edge between nodes ai and bi.

Return an array answer of length n where answer[i] is the total distance (sum of edge lengths along shortest paths) from node i to every other node in the tree.

Example 1:

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

Output: [8,12,6,10,10,10]

Explanation: The tree is shown above.

We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)

equals 1 + 1 + 2 + 2 + 2 = 8.

Hence, answer[0] = 8, and so on.

Example 2:

Input: n = 1, edges = []

Output: [0]

Example 3:

Input: n = 2, edges = [[1,0]]

Output: [1,1]

Code

1

2

3

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]: