Link-cut treeで部分木更新をする

Link-cut treeで部分木になんか(sumとか)載せるやつを先に知っておくことを推奨します ( https://beet-aizu.hatenablog.com/entry/2019/06/08/221833 )
上の記事の更に読者層が限定されたバージョンです
さて、部分木にaddとかやりたくないですか ? やりたいですよね ???
Toptree使えばなんでもできるっていうのは置いといてLCTで頑張ってみます
扱えるのは遅延セグ木に乗るような作用素の要件に加えて作用素に逆元があって打ち消しが可能なやつです(例えばaddはこれを満たします)

遅延セグ木のノリで遅延を部分木に流そうとするとたくさん生えてるlight edge全部見ることになって多分大変なことになります
これは親からたくさんある子に一気に流すのが悪いので、代わりに必要なときに子から親の遅延情報を引っ張ってくる感じで伝播させます。
具体的にはsubtree addでは

• heavy edgeへもlight edgeへも同じ遅延情報を使う

• 各ノードは変数added, cancel, sumを持つ(それぞれ初期値0)

• subtree addするときはcutしてexposeしてそのノードのaddedに足したい分だけ足す(その後cutしたのを繋ぎなおす)

• addedの伝播
  ノードxが親から遅延情報取ってくるとき

  1. x->added += x->parent->added - x->cancel
  2. x->sum += x->size * (x->parent->added - x->cancel)
  3. x->cancel = x->parent->added

  をします。
  たくさんあるlight edgeで繋がった子から違うタイミングで使われるのでaddedは絶対にクリアされません。
  ただそれだと同じ遅延情報を2回3回引っ張ってきてしまうのでcancelに「最後に親から取ってきたときの親のadded」を入れておくことで差分だけ取ってくるようにします。
  親が変わるときは適切にx->cancelをx->parent->addedに合わせる必要があります。(特にrotateとかでheavy edgeをいじるだけのときもやります)
  また、必然的に(「ノードxの遅延情報はこれからノードxに適用するもの」方式に対して)「ノードxの遅延情報はノードxに既に適用されている」方式を取ることになります。

コードは... よすぽさんのgithub
このコードではevertのreverse遅延は「ノードxの遅延情報はこれからノードxに適用するもの」方式をとっています。紛らわしいですね
なお一箇所オーバーフローさせてhotmanさん困らせてましたごめんなさい。