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