Изменения
→Вычисление LCA
====Вычисление LCA====
Пусть требуется найти LCA для двух вершин. Для этого будем рекурсивно подниматься от этих вершин в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, <tex>v</tex>. Заметим, что если эти вершины лежат на одном пути, то мы нашли ответ: LCA будет та, которая ближе к корню, т.е расстояние от корня до которой минимально. Очевидно, что если расстояние от <tex>u</tex> до корня меньше, чем расстояние от <tex>v</tex> до корня, то <tex>u</tex> является предком <tex>bv</tex>, а не наоборот.
Для проверки этого условия недостаточно знать только корни путей. Потому что бесконечно большое количество путей могу иметь общий корень. Но любые два пути пересекаются не более чем в одной вершине. Воспользуемся этим фактом.
