Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, <tex>v</tex>.
Пусть вершина <tex>Aa</tex> {{---}} первая вершина пути из предка вершины <tex>u</tex> в вершину <tex>u</tex>, а <tex>Bb</tex> {{---}} первая вершина пути из предка вершины <tex>v</tex> в вершину <tex>v</tex>.
Сравним вершины <tex>A</tex>* Заметим, что если <tex>B</tex>: * <tex>Aa</tex> = <tex>Bb</tex>. <br />Или , то или <tex>u</tex> лежит на пути от корня к <tex>v</tex>, или наоборот. За LCA примем ту вершину, которая лежит ближе к корню, т.е расстояние от корня до которой минмиально.* Очевидно, что если расстояние от <tex>Aa</tex> до корня меньше, чем расстояние от <tex>\not=b</tex> , то корня, то <tex>Ba</tex>.является предком <tex>b<br /tex>Нужно приблизить одну , а не наоборот. * Иначе, вершины лежат на разных путях, значит ответ не изменится, если вместо одной из вершин к корнювзять корень того пути, выбрав вместо нее её предкана котором она лежит. Приближать Эту операцию будем на основании тогопроизводить с той вершиной, какая из вершин останется дальше чей предок наименее удален от корня, после приближения. Рекурсивно запустимся от выбранной и оставшейся вершин.
