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