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