size[v] nodes get closer. All other n−size[v] nodes get farther. Therefore answer[v]=answer[u]+n−2*size[v].

Root the tree once at 0 and record parent-before-child order. Reverse that order to compute subtree sizes and each subtree’s total distance from its root. The root’s subtotal becomes its all-node answer. A second forward pass applies the reroot equation along each parent-child edge. Unique tree paths ensure that exactly one of the two sides becomes closer; there are no alternative cycle routes to complicate the distance change.

What the function promises: n vertices and edges form a connected undirected tree on 0..n−1. Return each vertex’s sum of unweighted distances to all vertices. Empty input returns [] as a helper extension.

def distance_sums(n, edges):
    if n == 0:
        return []
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    parent = [-1] * n
    order = [0]
    for u in order:
        for v in graph[u]:
            if v != parent[u]:
                parent[v] = u
                order.append(v)
    size, subtotal = [1] * n, [0] * n
    for u in reversed(order[1:]):
        p = parent[u]
        size[p] += size[u]
        subtotal[p] += subtotal[u] + size[u]
    answer = [0] * n
    answer[0] = subtotal[0]
    for u in order[1:]:
        p = parent[u]
        answer[u] = answer[p] + n - 2 * size[u]
    return answer

assert distance_sums(3, [(0,1), (1,2)]) == [3,2,3]
assert distance_sums(4, [(0,1), (0,2), (0,3)]) == [3,5,5,5]
assert distance_sums(1, []) == [0]

Work and storage: O(V) time and space on a tree. Each edge participates in a constant number of updates. Both passes are iterative, so a long chain does not overflow recursion.

When to recognize it: Moving the root across an edge makes one whole side closer and the other side farther. Reuse the previous answer.

Check before applying it: The formula depends on a tree edge separating exactly two sides. Extra cycle edges destroy that partition argument.

Yes. Along u→v, every node on v’s side gets w closer and every other node gets w farther. Use answer[v]=answer[u]+w*(n−2*size[v]), and multiply the upward size contribution by w as well.