Изменения
→Вычисление LCA
Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, <tex>v</tex>.
Пусть <tex>a</tex> и <tex>b</tex> {{---}} вторые вершины путей, содержащих вершины <tex>u</tex> и <tex>v</tex> соответственно. Важно заметить, что любая вершина, помимо корня дерева является некорневой вершиной какого-либо другого пути, поэтому такие <tex>a</tex> и <tex>b</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>, а не наоборот.
