Compute sum of distances from each node to all others. Naive: . Rerooting: . Pass (post-order): compute and = sum of distances within subtree rooted at . Pass (pre-order): for each node, combine subtree answer with "rest of tree" answer from parent.
When moving root from to child : nodes in 's subtree get 1 closer (there are ), nodes outside get 1 farther (there are ). New answer = old difference.