Link-Cut tree
木をパスの素集合に分解して，それぞれのパスをスプレー木で表します．各パスの親になる頂点へ向かって辺を貼ることでパス同士の連結関係を表すみたいな感じ．平衡二分探索木で表しているのでsplit/mergeの要領で色々操作ができてうれしい．
このスライド がさいきょう
この記事 もさいきょう
スプレー操作は wikipedia がわかりやすかった
スプレー木で木を管理するので今見ているものが元の管理する対象の木なのかスプレー木の方なのかごっちゃにしないように注意
スプレー操作
頂点 にアクセスする場合，回転（スプレー操作と呼ばれる）を繰り返し頂点
を木の根に移動させる．スプレー操作には3種類が存在し，頂点
と頂点
の親の頂点
の位置関係でどの操作を行うか決まる．
zig
頂点 の親が根の場合に実行される．頂点
が根に来る方向に1度回転する．
zig-zig
と
のどちらも共にに右の子の場合，どちらも左の子の場合実行される．
を一段上げたあと，
を一段上げる方向に回転をする．
zig-zag
を一段上げ，もう一段上げる方向の回転する．
この操作はamortized
これを使うとexposeができる
exposeではスライドのp22の通り，「スプレーして根につなげたいパスへの辺をつなげる」を繰り返す
各種操作
koprickyさんの My Algorithm : kopricky アルゴリズムライブラリ をベースに，ei1333さんの Link-Cut木(Link-Cut-Tree) | Luzhiled’s memo を参考に抽象化しました
根から頂点vについて見たいときはexpose(v)
頂点uからvについて見たいときはevert(u), expose(v)
- lca(id1, id2)： 頂点id1とid2のLCAを求める
expose(id1) で根からid1までをつなげる．このパス上にLCAは存在するので expose(id2) で上にたどっていき，たどり着いた頂点がLCAとなる． - link(id1, id2)： 頂点id1とid2を結ぶ辺を追加する
expose(id1), expose(id2) したあと id1 の右の子を id2 にする
expose(id1) したタイミングではid1は属するパスの最後尾なのでsplayして根にすれば右の子は必ず空 - cut(id)： 頂点idと親を結ぶ辺を削除する
expose(id) したあと id の左の子との接続を消す
idに親が存在するならば，パスで一つ上なのでidの左の子が該当する - cut(id1, id2)： id1とid2を非連結にする
expose(id1), expose(id2) としたときに，
→ id1 がスプレー木の根： id1が属するパスからid2が属するパスへの辺がparなのでそれを消す
→ otherwise： 根からid2のパス上にid1が含まれる．id2よりもid1が浅いのでid2の左の子との辺を消す - connected(id1, id2)： 頂点id1, id2が連結か？
expose(id1), expose(id2) としたあと id1->par==nullptr(つまりsplay木の根) だと非連結
expose(id2) してるので id1 と id2 が連結なら id2 が根にくる
id1 == id2 がコーナーで id1 が根にくるが同一頂点なので連結 - evert(id)： 頂点idをsplay木の根にする
expose(id) したあと根の属するパスの向きを反転する - depth(id)： 頂点idの深さを求める
expose(id) したあと根の属するスプレー木の要素数を求めると根からidまでのパスの長さになる - toRoot_range(id, x)： 根から頂点idのパスに演算(xを作用)
- toRoot_query(id)： 根から頂点idのパスの演算結果を求める
expose(id) した後，根に 作用/値取得 のどちらかを行う - range(id1, id2, x)： 頂点id1からid2のパスに演算(xを作用)
- query(id1, id2)： 頂点id1からid2のパスの演算結果を求める
evert(id1), expose(id2) すると根が属するパスがid1からid2のパスになる - get_kth(id1, id2, k)： 頂点id1からid2のパスでk番目の頂点は何か？
evert(id1), expose(id2) して該当するパスのsplay木を根に持ってくる
splay木のk番目の頂点を求めるには二分探索すればよい
f,g,h は遅延セグ木と大体同じ
f: 子の要素の値をマージする
g: 作用する 部分木のサイズに応じて異なる結果となる（e.g. 区間和）などのために部分木のサイズを渡している
h: 作用素のマージ
s: 可換でない演算の場合のために，パスを反転するときのために値を計算する
この抽象化じゃ十分じゃなくない？
QTREE3みたいに頂点の値と和の型が違う場合とかありそう
問題例
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4087668#1
LCAの確認
根によってLCAは変わるのでevert(0)が必要なのに注意
https://atcoder.jp/contests/njpc2017/submissions/9287639
connected，link，cut の確認
https://yukicoder.me/submissions/413584
range，query の確認
パスに一様加算・パスの和 なのでいつものモノイド
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4086293#1
range, query の確認
ちょっと複雑だけどモノイドになってるのではい
可換ではないのでevertで反転するときにはちょっと注意が必要
https://atcoder.jp/contests/joisc2015/submissions/9290337
link, connected, range, query の確認
辺属性クエリは頂点に変換すると楽
パスに代入・パスの和 なのでモノイドなのははい
SPOJ QTREE1
https://ideone.com/Lpb1xw
辺属性で 点更新 & パスのmaxクエリ
複数テストケースなのでデストラクタをちゃんとする
SPOJ QTREE2
https://ideone.com/xxHXYd
パスの距離クエリ & パスでk番目に現れる頂点
getkth は evert(b), expose(a) した後，根が属するsplay木を二分探索
部分木クエリ
パスだけじゃなくて部分木の情報をもってうまいことやる
exposeでlight-edgeを切り貼りするところに処理を組み込める
Link Cut Treeで部分木の情報を管理する - beet's soil
各頂点に
- その頂点の値 (型KEY)
- 部分木の値の和 (型SUM)
SUMのメンバ関数として- merge: 左の子の部分木，自身の値，右の子の部分木の値をマージ
- toggle: evertするときに反転する
- add: light-edge → heavy-edge にするときの処理
- erase: heavy-edge → light-edge にするときの処理
点更新パスクエリ部分木クエリみたいなのができるっぽい
exposeとかsplayとかでmergeするのがうまくできるならok…？
あとevertで反転するやつが高速にできるならok…？
QTREE LCT + Dynamic Distance Sum - ei1333の日記
Vertex Add Subtree Sum
https://judge.yosupo.jp/submission/2752
その頂点を根とする部分木の和の情報を各頂点に持たせたい
部分木の和(=ret) = 頂点の値 + heavy-edgeでつながってる子の分 + light-edge でつながってる分(=splay木の右の子の分)
splay木の左の子の分は元のグラフで頂点の祖先なので部分木には足さない
splay木の右の子の分として足すべきなのはretではなくて，splay木の右の子の左の子の分も足すべき
retにsplay木の左の子を足したものをallとして保持しておく
heavy-edge でつながってる子の情報(=laz)がほしい
→ exposeでlight-edgeを切り貼りするところで処理する
→ add/erase でそれぞれ laz += all, laz -= all をすればいい
他にも色々できるっぽいけどわからん
抽象化もわからん
