Изменения

Построим [[Дерево отрезков. Построение|дерево отрезков]] над каждым путём. Рассмотрим запрос <tex>sum(u, v)</tex>. Найдем вершину <tex>c</tex>, которая является <tex>\mathrm{LCA}(u, v)</tex> (например с помощью [[Метод двоичного подъема|двоичного подъема]]. Мы разбили запрос на два: <tex>(u, c)</tex> и <tex>(c, v)</tex>, на каждый из которых можно легко ответить разбив его на множество путей из декомпозиции и ответив на каждый путь из этого множества по отдельности за <tex>O(\log{n})</tex> с помощью дерева отрезков на этом пути. Всего таких путей нужно будет рассмотреть <tex>O(\log{n})</tex>. Итого мы способны решить эту задачу за время <tex>O(\log^2{n})</tex>.

|statement=Пусть есть две вершины <tex>u</tex>, <tex>v</tex>, лежащие на разных путях. При этом <tex>U</tex>, <tex>V</tex> — корни путей, на которых они лежат. Если <tex>U</tex> более удален от корня, чем <tex>V</tex>, то <tex>\mathrm{LCA}(u, v) </tex> = <tex>\mathrm{LCA}(U, v)</tex>.

|proof=Пусть Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA }</tex> не равны. Значит Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Но Значит <tex>\mathrm{LCA }</tex> должен принадлежать двум путям. Однако , но по предположению пути на не пересекаются. Тем самым пришли к противоречию.

Рассмотрим Теперь рассмотрим случай, когда пути пересекаются. Пути не могут пересекаться совпадать более, чем в одной вершине, так как построенная декомпозиция является реберно-непересекающейся. В данном случае При этом корень одного из путей является вершиной другого(либо корни совпадают, что равносильно), поскольку в противном случае пути пересекаются в более чем 1 вершине, что противоречит предыдущему условию. <tex>\mathrm{LCA }</tex> должен принадлежать двум путям, значит именно этот корень и будет <tex>\mathrm{LCA}</tex>.

Построим heavy-light декомпозициюдля данного нам дерева. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:

# Корень пути, на котором лежит текущая вершина. <br />Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева. Очевидно, что имея разбиение на пути, найти корень можно за <tex>O(1)</tex>.

Пусть требуется найти Найдем <tex>\mathrm{LCA }</tex> для двух вершин. Для этого будем рекурсивно подниматься от этих вершин в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, и <tex>v</tex>. Заметим, что если эти вершины лежат на одном пути, то мы нашли ответ: LCA будет та{{---}} это такая вершина (<tex>u</tex> или <tex>v</tex>), которая находится ближе к корню, т.е расстояние от корня до которой минимально. Очевидно, что если расстояние от корня до <tex>u</tex> до корня меньше, чем расстояние от до <tex>v</tex> до корня, то <tex>u</tex> является предком <tex>v</tex>. Иначе, а не наоборот.

Для проверки этого условия недостаточно знать только корни путей. Потому , потому что бесконечно большое количество несколько путей могу иметь общий корень. Но любые два пути пересекаются не более чем в одной вершине. Воспользуемся этим фактом.

* Заметим, что если <tex>a</tex> = <tex>b</tex>, то или <tex>u</tex> лежит на пути от корня к и <tex>v</tex>, или наоборотлежат на одном пути. Этот случай мы уже рассмотрели ранее.

* Если это не так, то вершины лежат на разных путях. По лемме, т.к так как пути реберно не пересекаются, то ответ не изменится, если вместо одной из вершин взять корень того пути, на котором она лежит. Эту операцию будем производить с той вершиной, чей предок наиболее удален от корня. Рекурсивно запустимся от выбранной и оставшейся вершин.

 Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем <tex>\mathrm{LCA}</tex>.