Изменения
Нет описания правки
'''Heavy-light декомпозиция''' {{---}} техника разбиения дерева на множество рёберно-непересекающихся путей так, чтобы при прохождении от одной вершины до другой произошла смена не более, чем <tex>O(\log{n})</tex> путей.
==Описание задачи==
Пусть у нас есть дерево <tex>T</tex> c <tex>n</tex> вершинами и нам нужно проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>. Множество подобных запросов делаются за время <tex>O(\log^p{n})</tex> при Heavy-light декомпозиции.
==Описание декомпозиции==
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>
