Link Cut Treeを書いてみた
色んな人のプログラムをみて「へー」とか「ほー」とか言いながらつぎはぎして書いたらヤバイことが起きた
対象プログラム pic.twitter.com/JMz5AC88vL
— むげーーーーーん (@mugen_1337) 2021年4月24日
get_rootした後splay(root)しない
— むげーーーーーん (@mugen_1337) 2021年4月24日
(昨日みさわさんにヤバイと教えてもらった方) pic.twitter.com/YCNdSHlFX8
splay(root)をします pic.twitter.com/mCJuaP7WxR
— むげーーーーーん (@mugen_1337) 2021年4月24日
これ,それはそうだった.
頑張ってSplay木を深くまで潜ってrootを引っ張ってきたとき,splay木の形が一切変わらずに,もっかい同じクエリが来るとヤバイ!
それはそう
rootを見つけてきて,splay(root)をするとよくて,こうなると,splay木の形がイイ感じになるので,もっかい同じクエリが来ても,イイ感じの木を探索するので,大丈夫になる.
1つ気づいたこととして,布団の中でLink Cut Treeについて想いを馳せると,木のrootとsplay木のrootを混同して死ぬ.
起きて紙でしっかり考える