Изменения
→Реализация
Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем LCA.
===РеализацияПсевдокод===
<code>
# Находит наименьшего общего предка вершин '''u''' и '''v'''
'''def''' lca('''int''' u, '''int''' v):
# Проверяем вершины, в которые идут ребра из предков.
'''if''' (turn[u] == turn[v]):
# Ответ найден, выберем ближайшую к корню.
'''if''' (dist[u] < dist[v]):
'''return''' u
'''else''':
'''return''' v
# Приблизимся к корню. Выбираем наиболее удаленную вершину.
'''if''' (dist[last[u]] > dist[last[v]]):
'''return''' lca(last[u], v)
'''return''' lca(last[v], u)
</code>
===Ассимптотика===
