102
правки
Изменения
Нет описания правки
Итого мы рассмотрели корень каждого пути за <tex>O(1)</tex>, а путей всего <tex>O(\log{n})</tex>. И в последнем пути один раз запустили бинпоиск, который отработал за <tex>O(\log{n})</tex>. Итоговая асимптотика <tex>O(\log{n})</tex>.
==Реализация==
Опущены некоторые детали реализации: построение и предподсчётдерево отрезков.
<ul>
<li><tex>\mathrm{pathPos}</tex> {{---}} функция, позволяющая найти смещение вершины в пути относительно корня пути,</li>
<li><tex>\mathrm{getValue(\mathtt{i}, \mathtt{j})}</tex> {{---}} функция, позволяющая найти вес <tex>\mathtt{j}</tex>-ого ребра в <tex>\mathtt{i}</tex>-ом пути.</li>
Пример реализации запроса суммы на пути:
<code>
'''int''' query('''int''' u, '''int''' v):
'''int''' res = 0
'''int''' root = pathRoot(корень пути, в котором находится u) '''while''' '''not''' (root '''is ancestor of''' не является предком v) : <font color=green>// поднимаемся до тех пор, пока наш путь не содержит общего предка u и v</font> segmentTree = дерево отрезков, соответствующее путю в котором лежит u res += queryPath(getPathsegmentTree.sum(u), 0, pathPos(u)) u = '''parent of''' предок root <font color=green>// вырезали нижний путь и подняли нижнюю вершину до нижней вершины следующего пути</font> root = pathRoot(корень пути, в котором находится u) root = pathRoot(корень пути, в котором находится v) '''while''' '''not''' (root '''is ancestor of''' не является предком u) : <font color=green>// аналогично прошлому while, но с другой стороны</font> segmentTree = дерево отрезков, соответствующее путю в котором лежит v res += queryPath(getPathsegmentTree.sum(v), 0, pathPos(v)) v = '''parent of''' предок root root = pathRoot(корень пути, в котором находится v)
<font color=green>// последний путь (тот, что содержит общего предка) обрезан с двух сторон полученными вершинами</font>
segmentTree = дерево отрезков, соответствующее путю в котором лежит u res += queryPath(pathsegmentTree.sum(u), min(pathPos(u), pathPos(v)), max(pathPos(u), pathPos(v)))
'''return''' res
</code>
