Graph Theory37 sections · 1633 units
Open in Course

CSES 1132 Tree Distances I - Core Idea

Reuse diameter endpoints

For each node, the farthest node from it is one of the two diameter endpoints. Why? Because the diameter is the longest path in the tree, so its endpoints are the farthest apart.

So you can run BFS from both diameter endpoints, then for each node take the max of its distance to endpoint 11 and endpoint 22.

Total: three BFS runs (two to find diameter, two to compute distances from endpoints, but you reuse one).