HLD, Link-Cut, линейное MST (21 мая 2018)

  1. LCA: алгоритм Тарьян (из забытого старого)

  2. [15 минут] Heavy-Light decomposition
    1. Идея: разбиение дерево на пути, каждая вершина ровно в одном пути.
    2. Лемма про число прыжков: на любом пути к корню не более log2n прыжков между путями.
    3. Тонкости реализации (как создать HLD, как прыгать по ней вверх, как считать функцию на пути без LCA)
    4. Общая идея решения задач: сперва решить на отрезке массива деревом отрезков или BST, затем обобщить до путей на дереве, добавив HLD
    5. Признаки задачи, к которым применимо HLD: задача про дерево, в дереве меняются веса вершин/рёбер
    6. Организация кода так, чтобы можно было считать функцию и на пути, и на поддереве

  3. [30 минут] Link-Cut-Tree
    1. Идея: динамическое разбиение вершин корневого дерева на пути. База: каждая вершина − самостоятельный путь.
    2. Операция Expose, время работы k*logn.
    3. Амортизированное оценка на k = O(logn). Потенциал − число тяжелых рёбер, покрытых путями.
    4. Операция MakeRoot. Изменение потенциала − не более чем число лёгких рёбер на пути, то есть, O(logn)
    5. Функция на пути дерева; link(a,b), cut(a,b): MakeRoot(a) + MakeRoot(b) + O(1)
    6. Сравнение с Euler-Tour-Tree: кроме link и cut умеет считать функцию на пути, находить lca
− Перерыв −
  1. [35 минут] MST за линейное время
    1. Проверка MST на минимальность за линейное время (ссылаемся на RMQ за O(1), которым на самом деле не владеем)
    2. Алгоритм = 3 шаги Борувки + построить остов F от случайной половины рёбер + выкинуть F-тяжёлые + построить от оставшихся
    3. Лемма о количестве F-тяжёлых рёбер с доказательством: (n - 1)(1/p - 1)
    4. Оценка времени в среднем O(n+m)
    5. [skipped] [ушло на практику] Оценка времени в худшем min(O(n2), O((n+m)logn))