102
правки
Изменения
Нет описания правки
Пусть у нас есть дерево <tex>T</tex> c <tex>n</tex> вершинами и нам нужно проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>. Множество подобных запросов делаются за время <tex>O(\log^p{n})</tex> при Heavy-light декомпозиции.
==Описание декомпозиции==
[[Файл:Heavylight.png|thumb|right|300x150px|Пример разбиения на лёгкие/тяжёлые рёбра.]]Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>.
'''Тяжёлые ребра''' {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geq </tex> <tex dpi="150">\frac{s(u) / }{2}</tex>.
'''Лёгкие ребра''' {{---}} соответственно все остальные.
Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум <tex dpi="150">\frac{s(u)}{2}</tex> вершин, а также сама вершина <tex>u</tex>. Итого <tex>s(u) + 1</tex> вершин, тогда как у нас всего <tex>s(u)</tex> вершин в поддереве.
Теперь рассмотрим вершины, из которых не ведет ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что оно будет являться искомым.
