CSES 1133 Tree Distances II - Algorithm

$1.$ Root the tree at node $1$

$2.$ First DFS: compute subtree size and sum of distances from node $1$

$3.$ Second DFS: reroot the tree by moving from parent to child, updating the sum using the formula Formula: When moving root from $u$ to child $v$: - Nodes in subtree of $v$ (size $s_v$) get closer by $1$: subtract $s_v$ - Nodes outside subtree of $v$ (size $n - s_v$) get farther by $1$: add $n - s_v$ - New sum = old sum - $s_v$ + $(n - s_v)$ = old sum + $n - 2 \cdot s_v$

This runs in $O(n)$ time and uses $O(n)$ space.