234
правки
Изменения
→Решение задачи в частном случае
Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить величину <tex>\Delta w</tex>, которая равна разнице между весом вершины и весом её родителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:
<tex>w(u) = \sum _{v} \Delta w(v)</tex>, где суммаберется по всем предкам <tex>u</tex>, включая саму вершину.
При прибавлении <tex>\alpha</tex> на пути от вершины <tex>v</tex> до корня, сначала вызывается <tex>splay(v)</tex>, после чего в левом поддереве находятся вершины, которые лежат на пути к корню. Затем надо прибавить <tex>\alpha</tex> к <tex>\Delta w(v)</tex> и, чтобы сохранить веса вершин, которые находятся ниже в пути, вычесть <tex>\alpha</tex> от <tex>\Delta w(right(v.right))</tex>.
[[Файл:Linkcut_weights.png|250px|thumb|right|]]
= min\{0, \ \Delta min(l) + \Delta w(l), \ \Delta min(r) + \Delta w(r)\}</tex>
Чтобы найти минимум на пути, надо вызвать <tex>splay(v)</tex>, а затем сравнить минимум вес <tex>v</tex> и минимум её левого ребенка.
==Link-cut tree==
