Изменения
→Препроцессинг
Построим декомпозицию. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
# Расстояние до корня дерева. <br />Вычисляется за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину.
# Номер предкакорня текущего пути. <br /> Предком назовем ту вершину, которая является начальной в том пути, на котором лежит текущая вершина. Очевидно, что имея разбиение на пути, найти предка корень можно за <tex>O(1)</tex>.# Номер вершины, в которую выходит первое ребро текущего пути, ведущего из предка в вершину. <br />Аналогично, находится за <tex>O(1)</tex> при построении.
====Вычисление LCA====
