Изменения
Нет описания правки
Пусть дано корневое дерево <tex>T.</tex> На вход подаются запросы вида <tex>(u,\;v),</tex> для каждого запроса требуется найти их наименьшего общего предка.
== Алгоритм ==
=== Препроцессинг ===
1) В каждом узле будет храниться глубина узла в корневом дереве <tex>T.</tex>
:<tex>depth(u)= \begin{cases}
0 & u = root(T),\\
depth(v) + 1 & u = son(v).
\end{cases}</tex>
2) Ориентируем каждое ребро в дереве <tex>T</tex> и добавим обратное к этому ребру. Получим эйлеров граф <tex>E.</tex>. Найдем в графе <tex>E</tex> эйлеров цикл, записывая в массив глубину посещенных узлов.
3) Построим дерево отрезков по полученному массиву.
== См.также ==
