Link Cut Tree の get_root ヤバかった

Link Cut Treeを書いてみた

色んな人のプログラムをみて「へー」とか「ほー」とか言いながらつぎはぎして書いたらヤバイことが起きた

これ,それはそうだった.

頑張ってSplay木を深くまで潜ってrootを引っ張ってきたとき,splay木の形が一切変わらずに,もっかい同じクエリが来るとヤバイ!
それはそう

rootを見つけてきて,splay(root)をするとよくて,こうなると,splay木の形がイイ感じになるので,もっかい同じクエリが来ても,イイ感じの木を探索するので,大丈夫になる.

1つ気づいたこととして,布団の中でLink Cut Treeについて想いを馳せると,木のrootとsplay木のrootを混同して死ぬ.

起きて紙でしっかり考える