3622
правки
Изменения
м
→Реализация
'''int''' root = корень пути, в котором находится u
'''while''' root не является предком v <font color=green>// поднимаемся до тех пор, пока наш путь не содержит общего предка u и v</font>
segmentTree = дерево отрезков, соответствующее пути , в котором лежит u
res += segmentTree.sum(0, pathPos(u))
u = предок root <font color=green>// вырезали нижний путь и подняли нижнюю вершину до нижней вершины следующего пути</font>
root = корень пути, в котором находится v
'''while''' root не является предком u <font color=green>// аналогично прошлому while, но с другой стороны</font>
segmentTree = дерево отрезков, соответствующее пути , в котором лежит v
res += segmentTree.sum(0, pathPos(v))
v = предок root
