Graph Theory37 sections · 1633 units
Open in Course

CSES 1132 Tree Distances I - Lessons

core idea

The farthest node from any node is always one of the diameter endpoints. This is an effective observation that turns an O(n2)O(n^2) problem into O(n)O(n). The pattern: find extremal points first, then use them to answer queries. This appears in many geometry and tree problems.

Diameter endpoints act like "anchors" that bound all other distances. When you see "for each node, find X" in a tree problem, ask whether extremal nodes or rerooting can avoid the O(n2)O(n^2) blowup.