\Section{Много всего}{11 марта}{Даниил Смирнов}

\Subsection{Euler-Tour-Tree}
  
    Эйлеров обход --- $2(n - 1)$ ребро. Храним их в Treap по неявному ключу.
    Несколько компонент --- несколько Treap.
    Решаем задачу ``добавлять и удалять рёбра, проверять связность вершин, в каждый момент времени граф не содержит циклов''.
    \begin{MyList}
        \item Link(a, b):\\
            1. делаем $a$, $b$ корнями соответствующих деревьев; \\
            2. Merge(Tree(a), $a \rightarrow b$, Tree(b), $b \rightarrow a$)
        \item Cut(a, b):\\
            1. у ребра $(a, b)$ есть два вхождения в Treap, удалим их, этой операцией мы вырезаем из дерева поддерево под ребром.\\
            2. соединяем префикс и суффикс --- получили два дерева.
        \item isConnected(a, b): root(a) == root(b); Храним у вершин дерева предков: тогда подъем в корень за $\log n$
    \end{MyList}

\Subsection{HLD -- Heavy Light Decomposition}
    \begin{MyList}
        \item Разбиваем пути на два вертикальных --- LCA
        \item Нужно, чтобы отвечать на запросы на пути дерева за $\log ^ 2$
            Разбиваем подвешенное дерево на пути. Путь строим в сторону наибольшего поддерева.
            На каждом пути строим дерево отрезков. Еще для путей храним len[path], top[path]
            --- длину и верхнюю вершину каждого пути. Для каждой вершины известен номер и 
            позиция на пути. 
    \end{MyList}
    Ответ на запрос: пока не в корне, делаем запрос к ДО текущего пути, затем поднимаемся в 
    предка вершины пути \\
    Время: $k \log n$, где $k$ --- число путей. Их не очень много. Докажем: смена пути 
    эквивалентна проходу по легкому ребру. Это увеличивает поддерево как минимум в два раза 
    --- не более $\log$ подъемов. 
    Тяжелые ребра проходятся сразу, так как лежат в одном пути в HLD.

\Subsection{Link-Cut Tree (без доказательства времени)}

    HLD + Link/Cut, Distance(a, b) \\
    Работаем за $\log ^ 2$. Добавим Splay-деревья $\rightarrow \log$ \\
    Путь --- снова декартово дерево по неявному ключу. Храним вершины \\
    Вводим операцию Expose(a) --- соединяет $a$ с корнем, что они еще и лежат в одном 
    декартовом дереве. Поднимаемся до корня, как в HLD. По пути отрезаем ответвления и 
    прицепляемся сами. Кроме того отрежем от получившегося пути всё, что ниже $a$. Теперь $a$ и корень -- два конца одного пути.
    \begin{Lm} 
      $\sum k_i \leqslant (m + n) \cdot \log n$, где $k_i$ -- число прыжков между путями во время $i$-го Expose.
    \end{Lm}
    Выразим операции через него:
    \begin{lstlisting}[gobble=8]
        MakeRoot(a) {
            Expose(a);
            Reverse;
        }

        Distance(a, b) {
            MakeRoot(a);
            Expose(b);
            return size;
        }

        Link(a, b) {
            MakeRoot(b);
            parent[b] = a;
        }

        Cut(a, b) {
            MakeRoot(a);
            Expose(b);
            Split;
            parent[b] = -1;
        }
    \end{lstlisting}
