CSES 1132 Tree Distances I - Algorithm

$1.$ Run BFS from node $1$ to find one diameter endpoint $u$.

$2.$ Run BFS from $u$ to find the other endpoint $v$.

$3.$ Run BFS from $v$ (or reuse from step $2$).

$4.$ For each node $x$: answer = max(dist from $u$, dist from $v$).

Three BFS calls total: $O(n)$. This exploits the fact that diameter endpoints are the "extreme" nodes. Any other node's farthest point must be one of them.

Space complexity is $O(n)$ for the data structures used.