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