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