Центроидная декомпозиция (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.