heavy-light декомпозиция

Что значит восстановить путь в графе между двумя вершинами? Хеви-лайт декомпозиция делается на дереве и она просто разбивает его на не пересекающиеся по ребрам пути, причем если идти от любой вершины по направлению к корню, то мы сменим не более logN путей.

Недавно обсуждалось.

Ничего особо математического в том объяснении нету.
Строится декомпозиция так. Пусть S(v) - размер поддерева с корнем в вершине v (включая ее саму). Назовем ребро тяжелым, если оно идет из вершины v в потомок w, причем S(w)>=S(v)/2. Все остальные ребра назовем легкими. Теперь рассмотрим все вершины, из которых не выходит ни одного тяжелого ребра. Будем брать такие вершины по очереди и двигаться от них по направлению к корню, запоминая все ребра от начала пути. Как только мы прошли по легкому ребру или достигли корня - заканчиваем движение и запоминаем очередной путь. Легко понять, что все пути полученные таким образом не пересекаются по ребрам.
Как решать при помощи нее задачи. Например, нам поступают запросы, где нужно увеличивать все ребра на пути от А до Б на константу С, а так же искать длину пути от А до Б.
Заметим одно замечательное свойство этой декомпозиции. Если будем идти от любой вершины по направлению к корню, то мы сменим не более logN путей. Это объясняется тем что если идти от корня к любой вершине, то после прохождения по легкому ребру мы начинаем новый путь, а количество вершин в поддереве уменьшается минимум вдвое.
Чтобы решить ту задачу, заведем для каждого пути дерево отрезков. Теперь, когда поступает запрос - двигаемся по путям от А до LCA(A,B), а так же от B до LCA(A,B) и обновляем деревья отрезков. LCA(A,B) легко найти за O(logN) при помощи построенной декомпозиции (поднимаясь по путям и делая бинпоиск внутри первого пути, в котором лежит LCA). Искать расстояние так же. Таким образом, сложность решения выходит O(N * log^2(N)).