Sum of Distances in a Tree

n villages, numbered 0 to n - 1, are joined by the n - 1 footpaths in paths, each a pair [a, b], so that there is exactly one way between any two villages: the map is a tree. The distance between two villages is the number of footpaths on the way between them.

Write sum_of_distances(n, paths) that returns a list whose item i is the total of the distances from village i to every other village.

Examples

sum_of_distances(4, [[0, 1], [1, 2], [1, 3]])  # returns [5, 3, 5, 5]
sum_of_distances(3, [[0, 1], [1, 2]])  # returns [3, 2, 3]
sum_of_distances(1, [])  # returns [0]

In the first map, village 1 is next to all the others (1 + 1 + 1 = 3), while from village 0 the others are 1, 2 and 2 footpaths away, a total of 5.

Constraints

• 1 <= n <= 30,000, and the footpaths always form a tree.

Note

• The map can be a single chain of 30,000 villages. Python stops recursion at about 1,000 levels, so a recursive search has to be rewritten with a stack of your own.