Root the tree at node
First DFS: compute subtree size and sum of distances from node
Second DFS: reroot the tree by moving from parent to child, updating the sum using the formula Formula: When moving root from to child : - Nodes in subtree of (size ) get closer by : subtract - Nodes outside subtree of (size ) get farther by : add - New sum = old sum - + = old sum +
This runs in time and uses space.