Центроидная декомпозиция (12 марта 2021)

1. [30 минут] Центроидная декомпозиция
   1. Определение: центр, рекурсия, дерево центров, дерево вложенных компонент связности
   2. Построение за O(nlogn): ищем центр, рекурсия. Хранение за O(n): храним только дерево центров, вершины из дерева не удаляем, а помечаем.
   3. Выражение path(a,b) в виде суммы path(a,center)+path(center,b). Поиск центра: LCA в дереве центроидов.
   4. Код: calcSize, findCenter, buildCentroids, findLCA(a,b)
   5. Итог: получили мощную структуру, которая как минимум умеет считать любую функцию на пути в дереве за [O(nlogn), O(logn)].
   6. [skipped] [ушло в практику] Предподсчёт функции "минимум на пути дерева", удобное хранение: minOnPath[depth,v] − расстояния до центра уровня depth.