CSES 1133 Tree Distances II - Walkthrough - Tree Diameter & Center | Graph Theory

Tree: edges ( $1$ , $2$ ), ( $1$ , $3$ ), ( $3$ , $4$ ).

First DFS from node $1$ : size = { $1$ : $4$ , $2$ : $1$ , $3$ : $2$ , $4$ : $1$ }. Sum from node $1$ : distances are { $1$ : $0$ , $2$ : $1$ , $3$ : $1$ , $4$ : $2$ }, total = $4$ .

When you reroot from $1$ to $3$ : nodes in $3$ 's subtree ( $3$ , $4$ ) get $1$ closer, nodes outside ( $1$ , $2$ ) get $1$ farther. New sum = $4$ - $2$ + $2$ = $4$ .

This increment formula lets you compute all $n$ answers in $O(n)$ instead of $O(n^2)$ naive BFS from each node.