LeetCode 834 Sum of Distances in Tree - Implementation

function sumOfDistances(n, edges)
    // Build adjacency list
    // Pass 1 (down): compute count[v] and sum[v]
    dfs_down(0, -1)

    // Pass 2 (up): propagate answers
    ans[0] = sum[0]
    dfs_up(0, -1)

    return ans

Two passes using the rerooting technique. One pass down collects subtree info, one pass up distributes answers.

Time: $O(n)$. Space: $O(n)$.