1週間かけて満足のいく全方位木DPのライブラリを作成しました。あまりみた事のない思想な気がしたので思想部分をまとめています。
全方位木DPとは
https://github.com/BlueSugar620/math_optim-rs/blob/main/tree/rerooting/src/lib.rs
こちらになります。全ての頂点から木DPを高速で行いたいという要望に応えるアルゴリズムです。頂点数を \(N\) としたときに、 \(O(N)\) で動作します。
思想
こちらの二つの記事を参考にさせていただきました。ありがとうございます。
木DPをするにあたって、子から親に向かってデータをマージしていくイメージがあります。これをどのように一般化するかですが、データのマージを可換モノイドの演算ととらえました。ですが、求めたいデータが演算後のモノイドそのままとは限らず、そこにある変換をかけたものである可能性を考えました。
そこで、
- 頂点のデータをモノイドに変換
- モノイドを集約する
- モノイドをデータに直す
の3工程から考えることができると思いました。これを実装したものとなっています。
残るはngtkanaさんと内容は同じです。とても素晴らしい記事なのでぜひ読んでみてください。
数式による説明
後日書くかもしれません。
これはCTAサンプルです。
内容を編集するか削除してください。
