rerooting_monoid
コンセプト · 全方位木dp
template <class M, class W, class U>
concept rerooting_monoid =
monoid<M> && requires(const rerooting_key_t<M> &k, const typename M::value_type &s, const W &w, const U &u) {
{ M::f(k, w) } -> std::convertible_to<typename M::value_type>;
{ M::g(s, u) } -> std::convertible_to<rerooting_key_t<M>>;
};
概要
全方位木dp用モノイドの要件
集約型 value_type 上のモノイド（単位元 id・子の集約 op）に加えて、 辺を通す変換 f(確定値, 辺重み) -> 集約値 と、頂点で確定する変換 g(集約値, 頂点データ) -> 確定値 を持つこと。確定値型は key_type （省略時 value_type）。f / g は関数テンプレートでも非テンプレートでもよい。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
M |
判定対象のモノイド |
W |
辺重みの型 |
U |
頂点データの型 |
計算量
- コンパイル時の型制約のため実行時コストなし
関連項目
rerooting_key— 全方位木dp用モノイドの確定値型（key_type、省略時はvalue_type）rerooting_key_t— 全方位木 DP の確定値型Rerooting— 全方位木dp