LA, Heavy-Light Decomposition, Euler tour trees (10 марта)

  1. Euler Tour Trees
    1. идея, Эйлерово Обход Дерева, содержащий ориентированные рёбра
    2. ребро дерево ↔ вершина treap
    3. вершина дерева → рёбра дерева
    4. ребро → обратное ребро
    5. get(v): вершина дерева → ребро → вершина treap → подняться до корня treap
    6. makeRoot(v): start = any outgoing edge
    7. link(a, b): makeRoot(a), makeRoot(b), concat
    8. cut(a, b): makeRoot(a), e = (a, b), split off [e..rev(e)]
  2. Heavy-Light decomposition
    1. идея
    2. лемма про число прыжков
    3. тонкости реализации (как создать HLD, как прыгать по ней)
    4. общая идея решения задач: сперва решить на отрезке массива, затем обобщить до дерева, heavy-light обычно нужен только если дерево меняется
  3. LA
    1. Предподсчитаем всё (n2, 1)
    2. Двоичные подъёмы (nlogn, logn)
    3. heavy-light decomposition (n, logn)
    4. longest-path decomposition (n, sqrtn)
    5. ladder decomposition (nlogn, 1)
    6. Идея: храним двоичные подъёмы только от листьев (предподсчёт: dfs в offline)
    7. Микро-макро эвристика: Compress(tree, logn/4) + ответ на запрос
  4. Минимум на путях дерева в Offline за O*(1) [окончание]