Problem - Finding a Centroid

You are given a tree with $n$ nodes. Find any centroid. A centroid is a node where removing it leaves no component with more than $\lfloor n/2 \rfloor$ nodes. This is the foundation of centroid decomposition. If you can find one centroid efficiently, you can recursively find all of them.

The algorithm is simple but the Core idea is useful. Let me walk you through the solution step by step. You will use this as a subroutine in all centroid decomposition algorithms.