Центроид

Определение

Центроид дерева - такая вершина, если подвесить за которую, мощность любого из ее сыновей не превышает $\lfloor \frac{n}{2}\rfloor$, где $n$ - количество вершин дерева.

Алгоритм нахождения центроида

1. Выберите корень и для каждой вершины насчитайте мощность ее поддерева.
2. Если есть сын с мощностью хотя бы $\lceil \frac{n}{2}\rceil$, такой может быть только один, то перейдите в него и повторите второй пункт, иначе вершина, в которой мы остановились - центроид.
   Утверждение. Найденная вершина является центроидом.
   Доказательство. Предположим алгоритм закончил свою работу - $v$. Переподвесим дерево за нее, у всех вершин, что были подвешены к $v$, мощность не поменялась. Так как в алгоритме мы в них не зашли, то правда, что их мощность менее $\lceil \frac{n}{2}\rceil$. Вспомним интересный факт: $\lceil \frac{n}{2}\rceil -1\le \lfloor \frac{n}{2}\rfloor$. Значит у нас для потомков все верно. Если в изначальном алгоритме мы не делали ни одного шага, то и предка у нас не было и все хорошо, но если хотя бы один шаг был, то в изначальном дереве мощность $v$ хотя бы $\lceil \frac{n}{2}\rceil$. Вспомним еще один классный факт: $\lceil \frac{n}{2}\rceil +\lfloor \frac{n}{2}\rfloor =n$, а значит при переподвешивании у предка мощность будет не более чем $n-\lceil \frac{n}{2}\rceil =\lfloor \frac{n}{2}\rfloor$. Значит полученная вершина является центроидом по определению.
   Поиск в худшем случае, то есть бамбуке, займет $O(n)$ по времени.

Математические свойства центроидов

Так как мы нигде не пользовались свойствами самого дерева, то центроид существует в любом дереве, причем их может быть не более 2, так как в нашем алгоритме еще 1 центроидом может быть только предок найденного, если мощность его поддерева все-таки равна $\lfloor \frac{n}{2}\rfloor$.
Существует дерево центроидов, которое имеет логарифмическую высоту из-за свойств центроида, и позволяет считать разные функции на отрезках в дереве.
Центроид - идея бинарного поиска, примененная на дереве, ведь центроид для дерева, как и середина для массива, делит его пополам.