pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Link-Cut Treeの可視化(失敗作)

Link-Cut Treeをうまく可視化できないか考えてました。

exposeの可視化を目標としていましたが、うまい可視化が思いつかなかったので、あまり役に立たない可視化だけ公開します。察しのいい人なら実装まで想像がつくと思いますが、二分木のmerge/splitに慣れていない人だとこれだけを見て動作を理解するのは厳しいかと思います。

expose というのは頂点 u と根をパスで繋げるという操作です。

ChromeFirefoxでは少なくとも見れます。重くて見れない人はごめんなさい。

https://pekempey.github.io/link_cut_tree/lctree.html

高速版。lctreeの高速さが感じ取れます。
https://pekempey.github.io/link_cut_tree/lctree_fast.html

木の描画はいい感じのライブラリがあったら差し替えたいものです…(Reingold-Tilfordとかいうのが良さそうなのかな)