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