hardTreesPure DSA~40 min
Sum of Distances from Every Node in a Tree
In a tree-shaped service topology, you want, for each node, the total hop distance to all other nodes — to pick low-latency coordinators. Compute all answers in linear time.
Problem
Given an undirected tree of n nodes (0-indexed) described by edges, return an array result where result[i] is the sum of the distances (number of edges) from node i to every other node.
Input
An integer n and a list edges of n-1 undirected [u, v] pairs forming a tree.
Output
An array of n integers, the distance sums for each node.
Constraints
- 1 <= n <= 30000
- edges forms a valid tree with n-1 edges.
Examples
Example 1
Input
n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output
[8,12,6,10,10,10]
Node 2 is most central with total distance 6.
Example 2
Input
n = 1, edges = []
Output
[0]
A single node has zero total distance.