'''return''' p[v]
</code>
==Модификация предподсчета за O(n) времени и O(n) памяти==
Воспользуемся идеей [[Heavy-light декомпозиция|Heavy-light декомпозиции]], которая разбивает все вершины дерева на вершинно-непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log n</tex> различных путей.
===Препроцессинг===
Построим декомпозицию. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
# Расстояние до корня дерева.
# Номер предка {{---}} начало пути от корня, ведущего в вершину.
# Номер вершины, в которую выходит первое ребро пути, ведущего из предка в вершину.
===Вычисление LCA===
Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, <tex>v</tex>, пусть <tex>s</tex> {{---}} предок вершины <tex> u</tex>, а <tex> t</tex> {{---}} предок вершины <tex>v</tex>.
Пусть вершина <tex>A</tex> {{---}} первая вершина пути из <tex>s</tex> в <tex>u</tex>, а <tex>B</tex> {{---}} первая вершина пути из <tex>t</tex> в <tex>v</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 />Нужно приблизить одну из вершин к корню, выбрав вместо нее её предка. Приближать будем на основании того, какая из вершин останется дальше от корня, после приближения.
Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем LCA.
===Псевдокод===
<code>
<font color=darkgreen>// Находит наименьшего общего предка вершин '''u''' и '''v'''</font>
'''int''' lca('''int''' u, '''int''' v):
<font color=darkgreen>// Проверяем вершины, в которые идут ребра из предков.</font>
'''if''' (turn[u] == turn[v]):
<font color=darkgreen>// Ответ найден, выберем ближайшую к корню.</font>
'''if''' (dist[u] < dist[v]):
'''return''' u
'''else''':
'''return''' v
<font color=darkgreen>// Приблизимся к корню. Выбираем наиболее удаленную вершину.</font>
'''if''' (dist[last[u]] > dist[last[v]]):
'''return''' lca(last[u], v)
'''return''' lca(last[v], u)
</code>
===Ассимптотика===
* '''Память''': Для реализации алгоритма требуется <tex>O(n)</tex> памяти.
* '''Препроцессинг''': Heavy-light декомпозиция строится за <tex>O(n)</tex>.
* '''Запросы''': По свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более <tex>\log n</tex> путей. Значит время выполнения запроса также <tex>O(\log n)</tex>.
==См. также==
