読者層が限定されすぎていませんか？
Link Cut Treeを書いたことがない人はこちら！
ei1333.hateblo.jp
上の記事ではパスクエリを処理していましたが、頑張れば部分木クエリも処理できます
正確には木全体の情報を持つようにして、クエリが来たら部分木の根とその親の間の辺をcutします
実装はこちら！
github.com
〜完〜
記事の価値が無すぎるので忘備録も兼ねて解説もどきを書いておきます。
まず遅延評価は忘れます 不可能ではないと思うので誰か頑張ってください
点変更とかは適当にやればできますがとりあえず変更もないものとします
部分木クエリで扱えるのはアーベル群みたいなやつです よくわからないので検証が必要そう
これはどうしてかというとまず結合則がないと何もできません 単位元がないと実装がつらいです
exposeのときにくっつけたりちぎったりするので逆元がほしいです
子の情報をマージする順番が固定されていないので可換性も必要です
これらを満たす対象はアーベル群と呼ばれています
しかし、子を辺を通して持ち上げるときに処理を挟むことができます（ここがよく分からない）
実装方針は以下の通りです
まずノードに持たせる情報をvalとします
light edgeでつながっている子の情報をまとめたものをdatとします
valとdatと(heavy edgeでつながっている子の情報)をまとめたものをsumとします
まとめる操作(pushup)は例えば以下のように実装できます aiをAの単位元とします
inline A resolve(Node *t){ return t?t->sum:ai; } inline void pushup(Node *t){ if(t==nullptr) return; t->sum=t->val+t->dat; t->sum+=resolve(t->l); t->sum+=resolve(t->r); }
！！！
. +=と+は別の演算です 処理を挟む場合(+=) とそうでない場合(+)があるんじゃ
何を言っているか分からないかもしれないが僕もよく分からない
どういう風に使うかというと
using ll = long long; struct A{ ll sz1,sz2; A():sz1(0),sz2(){} A(ll sz1,ll sz2):sz1(sz1),sz2(sz2){} A operator+(const A &a)const{ return A(sz1+a.sz1,sz2+a.sz2); }; A& operator+=(const A &a){ sz1+=a.sz1; sz2+=a.sz1*a.sz1; return (*this); } A& operator-=(const A &a){ sz1-=a.sz1; sz2-=a.sz1*a.sz1; return (*this); } };
みたいにつかう これは部分木の子の連結成分の二乗和を求めている
！！！
なぜdatにheavy edgeの情報をまとめないかというと、splayしたときにdatを更新する必要がなくなるからです
rotateはうしさんの記事と同じようにやります
触ったノードは下からpushupでsumにまとめておきます
rotateだけの話ではなく常にsumはvalidになるようにしておきます
exposeのときはdatも更新する必要があります これは以下の二つのパートに分解できます
- 元の右の子の情報をdatにまとめる（heavy edgeからlight edgeになるので）
- 新しい右の子の情報をdatから取り除く（light edgeからheavy edgeになるので）
つなぎ替えた後にpushupするのを忘れずに
linkでは繋げた後親をpushupします
cutでは切ったあと元の木における子（splay木では親）をpushupします
可換性を要求しているのでevertでは特に何もする必要がないはずですが、verify問がないのでよくわかりません
(2019/06/11 更新) evertすると部分木の再計算がやばいので多分無理です
(2019/06/14 更新) 冷静に考えるとほとんどのlight-edgeはそのままなのでできそう 可換性を仮定しているのでsplay木上の左右の子を入れ替えても影響はないし （よくわからん 間違ってるかも）
このテクニックを使うと、例えば部分木の子の連結成分の二乗和等を求めることができます
Problem - E - Codeforces
おわりに
なんもわからん Top Treeの解説記事はよ
