Изменения
→Вычисление LCA
Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, <tex>v</tex>.
Пусть вершина <tex>a</tex> {{---}} первая вершина пути из предка вершины <tex>u</tex> в вершину <tex>u</tex>, а и <tex>b</tex> {{---}} первая вершина пути из предка вторые вершины путей, содержащих вершины <tex>vu</tex> в вершину и <tex>v</tex>соответственно.
* Заметим, что если <tex>a</tex> = <tex>b</tex>, то или <tex>u</tex> лежит на пути от корня к <tex>v</tex>, или наоборот. За LCA примем ту вершину, которая лежит ближе к корню, т.е расстояние от корня до которой минимально. Очевидно, что если расстояние от <tex>a</tex> до корня меньше, чем расстояние от <tex>b</tex> до корня, то <tex>a</tex> является предком <tex>b</tex>, а не наоборот.
