Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что с помощью такого трюка мы можем решить широкий класс задач просто сведя её к задаче о запросах в дереве отрезков (такие как максимум на пути, покраска на пути, прибавление на пути и др.).
==Реализация==
Здесь будет простая реализация Опущены некоторые детали реализации: построение и предподсчёт. <tex>path</tex> {{---}} массив, хранящий в себе номер пути в которому относится конкретная вершина, <tex>pathRoot</tex> {{---}} корень пути (самая верхняя вершина), <tex>pathPos</tex> {{---}} массив, хранящий смещение вершины в пути относительно корня пути. <tex>value[i][j]</tex> {{---}} вес <tex>j</tex>-ого ребра в <tex>i</tex>-ом пути. <code> '''function''' queryPath('''int''' path, '''int''' from, '''int''' to): '''int''' res = 0 '''while''' from <= to: '''if''' from % 2 == 1: res += value[path][from] '''if''' to % 2 == 0: res += value[path][to] to = (to - 1) / 2 from = (from + 1) / 2 '''return''' res '''function''' query('''int''' u, '''int''' v): int res = 0 int root = pathRoot[path[a]]; '''while''' !isAncestor(root, b) res += queryPath(path[a], 0, pathPos[a]); a = parent[root] root = pathRoot[path[a]] root = pathRoot[path[b]]; '''while''' !isAncestor(root, a) res += queryPath(path[b], 0, pathPos[b]); b = parent[root] root = pathRoot[path[b]] res += queryPath(path[a], min(pathPos[a], pathPos[b]), max(pathPos[a], pathPos[b])) '''return''' res</code> ==Примечание==Существует вариант Heavy-light декомпозициина вершинно-непересекающихся путях. Чтобы получить такой путь нужно всего-лишь выкинуть последнее ребро из всех путей в рёберно-непересекающейся декомпозиции.
== См.также ==
