How should I practice Sum of Weighted Distances in a Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Sum of Weighted Distances in a Tree associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Sum of Weighted Distances in a Tree

Google● HardNEW GRADONSITE INTERVIEW

Problem statement

You are given a tree with n nodes numbered from 0 to n - 1. Each row edges[i] = [u, v, weight] is an undirected edge between nodes u and v with a positive integer weight.

The distance between two nodes is the sum of the edge weights on the unique path between them.

Return an array answer of length n, where answer[i] is the sum of the distances from node i to every other node.

Function

sumOfWeightedDistances(n: int, edges: int[][]) → long[]

Examples

Example 1

n = 4edges = [[0,1,3],[1,2,1],[1,3,5]]return = [15,9,11,19]

Node 1 touches every other node. From node 1, the distances are 3 to node 0, 1 to node 2, and 5 to node 3, so answer[1] = 9.

From node 0, every path first crosses the weight-3 edge: the distances are 3, 3 + 1 = 4, and 3 + 5 = 8, so answer[0] = 15. In the same way, answer[2] = 1 + 4 + 6 = 11 and answer[3] = 5 + 8 + 6 = 19.

Example 2

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

There is only one node and no other node to reach, so its sum is 0.

Example 3

n = 3edges = [[0,1,10],[0,2,1]]return = [11,21,12]

From node 0, the distances are 10 and 1, giving 11. Node 1 reaches node 0 with distance 10 and node 2 with distance 10 + 1 = 11, giving 21. Node 2 has distances 1 and 1 + 10 = 11, giving 12. Counting edges alone would make nodes 1 and 2 look the same, but the weights make their sums different.

Constraints

1 <= n <= 6000
edges.length == n - 1
edges[i].length == 3
0 <= u, v < n and u != v
1 <= weight <= 10⁴
The edges form one connected tree.