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