FastPrepSum of Distances in Tree
Problem · Tree

Sum of Distances in Tree

Learn this problem
● HardGoogle logoGoogleINTERNONSITE INTERVIEW
See Google hiring insights

Problem statement

You are given a connected undirected tree with n nodes numbered from 0 to n - 1. The array edges contains the tree's n - 1 edges.

Return an integer array answer of length n, where answer[u] is the sum of the shortest-path distances from node u to every other node.

Function

sumOfDistancesInTree(n: int, edges: int[][]) → int[]

Examples

Example 1

n = 6edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]return = [8,12,6,10,10,10]

From node 0, the distances are 0, 1, 1, 2, 2, 2, which sum to 8. Repeating the definition for each root gives the returned array.

Example 2

n = 1edges = []return = [0]

The only node has distance 0 to itself.

Constraints

  • 1 <= n <= 30000
  • edges.length = n - 1
  • Every row of edges is [u, v] with 0 <= u, v < n and u != v.
  • edges forms one connected tree.

More Google problems

drafts saved locally
public int[] sumOfDistancesInTree(int n, int[][] edges) {
    // write your code here
}
n6
edges[[0,1],[0,2],[2,3],[2,4],[2,5]]
expected[8,12,6,10,10,10]
checking account