Compute distance-sum from every tree node

Q: Compute distance-sum from every tree node

This is a Coding & Algorithms interview question from Google for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

You are given an undirected tree with n nodes labeled 0..n-1 and a list of n-1 edges. The tree is connected and contains no cycles.

For each node i, compute:

$ans[i] = \sum_{j=0}^{n-1} dist(i, j)$

where dist(i, j) is the number of edges on the unique path between nodes i and j.

Input

Integer n
List edges , where each element is a pair [u, v] indicating an undirected edge between u and v

Output

An integer array ans of length n , where ans[i] is the sum of distances from node i to all nodes.

Constraints

1 ≤ n ≤ 2 * 10^5
edges.length = n - 1
0 ≤ u, v < n
The input graph is a tree.

Example

Input:

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

Output:

ans = [5,3,5,5]

Explanation:

From node 1 : distances to [0,2,3] are [1,1,1] , sum is 3 .
From node 0 : distances to [1,2,3] are [1,2,2] , sum is 5 .