Lessons from Distance Queries

Important lessons:

$1.$ Centroid decomposition reduces tree queries to queries about centroid ancestors

$2.$ The $O(\log n)$ depth bound keeps space and time manageable

$3.$ Any path in the tree passes through exactly one lowest common centroid ancestor

$4.$ LCA-based distance is simpler for this problem, but centroid decomposition extends to harder variants

When should you use centroid decomposition over LCA? When the problem involves updating nodes or more complex path properties.