Изменения

==Модификация предподсчета за <tex>O(n)</tex> времени и <tex>O(n)</tex> памяти==

Воспользуемся идеей [[Heavy-light декомпозиция|Heavy-light декомпозиции]], которая разбивает все вершины дерева на вершинно -непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log(n)</tex> различных путей.

# Номер предка. (Начало {{---}} начало пути от корня, ведущего в вершину).# Номер вершины, в которую выходит первое ребро пути, ведущего из предка, ведущее в вершину.

Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>Uu</tex>, <tex>v</tex>, пусть <tex>s</tex> {{---}} предок вершины <tex> u</tex>, а <tex> t</tex> {{---}} предок вершины <tex>v</tex>. Рассмотрим пути из <tex>s</tex> в <tex>u</tex> и из <tex>t</tex> в <tex>u</tex>.Пусть вершина <tex>A</tex> {{---}} первая вершина пути из <tex>s</tex> в <tex>u</tex>, а <tex>VB</tex> {{---}} первая вершина пути из <tex>t</tex> в <tex>u</tex>.  Сравним вершины (<tex>A</tex>, <tex>B</tex>), в которые идут ребра из предков рассматриваемых вершин. : * <tex>A</tex> = <tex>B</tex>. <br />Или <tex>U</tex> лежит на пути от корня к <tex>V</tex>, или наоборот. За LCA выберем примем ту вершину, которая лежит ближе к корню.* <tex>A</tex> <tex>\not=</tex> <tex>B</tex>. <br />Нужно приблизить одну из вершин к корню, выбрав вместо нее её предка. Приближать будем на основании того, какая из вершин останется дальше от корня, после приближения.

# <font color=darkgreen>// Находит наименьшего общего предка вершин '''u''' и '''v'''</font> '''defint''' lca('''int''' u, '''int''' v): # <font color=darkgreen>// Проверяем вершины, в которые идут ребра из предков.</font>

# <font color=darkgreen>// Ответ найден, выберем ближайшую к корню.</font>

# <font color=darkgreen>// Приблизимся к корню. Выбираем наиболее удаленную вершину.</font>