えびちゃんの日記

えびちゃん（競プロ）の日記です。

全方位木 DP を指して rerooting と呼ぶ風潮に対するお気持ち表明

rerooting DP、rerooting をする DP、DP with rerooting とかなら別によさそう。

全方位木 DP 自体を指して「rerooting」と言われると気になります。 rerooting は木の根を変える操作（全方位木の中で考えられる）を指していて、全方位木 DP 自体のことを指しているわけではないと思っています。

例を出すよ

DP 以外の文脈で rerooting という言葉が使われているのを挙げてみます。 Euler tour を管理するデータ構造で、根とする頂点を変える操作が rerooting と呼ばれています。

http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/17/Slides17.pdf

上の資料では、森に関するクエリ処理をするデータ構造を考えています。 対象のクエリは「この辺を追加してね」「この辺を削除してね」で、ループはできないことが保証されています。

森を Euler tour の集合として表現すると、辺の追加や削除に際して、Euler tour の根の頂点を変える操作ができると楽になるようです。 そこで、その操作名が rerooting と呼ばれています。

例おわり。

DP の名前ではなくて、単に、より一般的な操作の名前として捉える方が自然な単語に思えます。

そういえば

splay tree ではアクセスしたノードを根に持っていく操作を splay と呼んでいましたね*1。

そこで思ったんですが、splay tree で splay をする際に DP の更新をするようにすれば、順に頂点をなめることで全方位木 DP で得たいものを得られたりしませんかね？ splay は amortized \(O(\log(n))\) time ですが、順になめたときは amortized \(O(\log(\log(n)))\) time という結果もあった気がします（詳細見失いました、嘘かも）。

何にせよ普通に BFS/DFS した方が速そうですが...

追加

twitter.com

twitter.com

おわり

もしかしたらえびちゃんの勘違いで、全方位木 DP 自体を指して rerooting と呼んでいる人はいないかもしれません？

お気持ち表明シリーズが好きな人におすすめ（今回の記事より内容ずっしりめです）： rsk0315.hatenablog.com

*1:link/cut tree では evert という呼ばれ方もあったような...？