LCA

Наименьшим общим предком, или LCA двух вершин $u, v$ в подвешенном дереве называется такая вершина на пути $u\rightarrow v$, что её глубина минимальна.

Поиск LCA

Самым популярным алгоритмом является метод двоичных подъёмов. Он позволяет с предподсчётом за $O(nlogn)$ искать $lca(u, v)$ за $O(logn)$. Идея вкратце - выбираем одну из вершин запроса, пробуем подняться из неё на $2^k, \ 2^{k-1}, \dots, 2^0$, если очередной подъём приведет нас в предка другой вершины запроса - остаёмся на месте, если же не приведёт - поднимаемся.

O(1) на запрос

Оказывается, можно получить время лучше. Для этого вместо двоичных подъёмов построим эйлеров обход дерева - массив, в котором записаны вершины в порядке обхода dfs, каждая вершина записывается при входе в неё из её предка или одного из сыновей. Заметим, что lca двух вершин будет лежать в эйлеровом обходе между вхождениями этих двух вершин, причём он на этом подотрезке будет иметь наименьшую глубину по определению lca. В таком случае для поиска минимума можно использовать sparse table и отвечать на запрос за $O(1)$.

Предподсчёт за O(n)

Оказывается, некоторым трюком можно ускорить прошлый алгоритм, сделав более быстрый предподсчёт. Тут не будет подробно разбираться, как это делается, однако это основывается на том, что в нашей задаче высоты соседних вершин отличаются на +-1. Подробнее об этом можно прочитать тут.

Dynamic lca

Иногда корень дерева может меняться. Ясно, что в таком случае $lca(u, v)$ тоже может меняться. Пусть $lca_r(u, v)$ - LCA двух вершин при подвешивании дерева за $r$. Оказывается, $lca_r(u, v) = lca_0(u, v) \ xor \ lca_0(u, r) \ xor \ lca_0(r, v)$.