tree_dp

コンセプト · Static Top Tree（木を rake / compress の二分木へ分解する）

template <class D>
concept tree_dp = requires(D &d, const typename D::Path &p, const typename D::Light &l, int u) {
    { d.vertex(u) } -> std::convertible_to<typename D::Path>;
    { d.add_vertex(p, l) } -> std::convertible_to<typename D::Path>;
    { d.add_edge(p) } -> std::convertible_to<typename D::Light>;
    { d.rake(l, l) } -> std::convertible_to<typename D::Light>;
    { d.compress(p, p) } -> std::convertible_to<typename D::Path>;
};

概要

Static Top Tree に載せる木DPの要件

重パス上の集約型 Path と軽辺クラスタの集約型 Light に対し、頂点の初期値 vertex、パスへの軽辺クラスタの付加 add_vertex、部分木から軽辺クラスタへの変換 add_edge、軽辺クラスタ同士の合成 rake、パス同士の連結 compress を持つこと。compress(p, c) の p は親側、c は子側で、非可換でよい。 DynamicTopTree も同じ要件のクラスを受け取る。

テンプレートパラメータ

名前	説明
`D`	判定対象の木DP

計算量

コンパイル時の型制約のため実行時コストなし

tree_dp

概要

テンプレートパラメータ

計算量

関連項目