Изменения
→LCA
Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что навесив дерево отрезков на каждый путь мы способны отвечать на любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде (операции, поддерживаемые деревом отрезков), такие как: сумма на пути, максимум на пути, количество рёбер на пути, удовлетворяющих какому-то свойству.
===LCA===
Задача о наименьшем общем предке для двух вершин в дереве с <tex>n</tex> вершинами решается с помощью heavy-light декомпозиции. Воспользуемся основной идеей: декомпозиция разбивает все вершины дерева на вершиннореберно-непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log{n}</tex> различных путей. ====Лемма====Пусть есть две вершины <tex>a</tex>, <tex>b</tex>, лежащие на разных путях. Пусть <tex>A</tex>, <tex>B</tex> - корни путей, на которых они лежат. Пусть <tex>A</tex> более удален от корня, чем <tex>B</tex>. Докажем, что <tex>LCA(a, b) </tex> = <tex>LCA(A, B)</tex>. ====Доказательство====.Пусть пути не пересекаются. Предположим, что LCA не равны. Значит существует вершина, на пути от <tex>a</tex> к <tex>A</tex>, являющаяся LCA. Но LCA должен принадлежать двум путям. Но пути на пересекаются (?!). Рассмотрим случай, когда пути пересекаются. Пути не могут пересекайся более, чем в одной вершине. В данном случае корень одного из путей является вершиной другого. LCA должен принадлежать двум путям, значит именно этот корень и будет LCA.
====Препроцессинг====
* Заметим, что если <tex>a</tex> = <tex>b</tex>, то или <tex>u</tex> лежит на пути от корня к <tex>v</tex>, или наоборот. Этот случай мы уже рассмотрели ранее.
* Если это не так, то вершины лежат на разных путях. ТПо лемме, т.к пути вершинно реберно не пересекаются, то ответ не изменится, если вместо одной из вершин взять корень того пути, на котором она лежит. Эту операцию будем производить с той вершиной, чей предок наиболее удален от корня. Рекурсивно запустимся от выбранной и оставшейся вершин.
