View on GitHub

cp-library

全方位木 DP

コラム一覧に戻る

自分のブログにリンクを貼りたくなったので、資料を別の URL に退避しました。

主な機能

ユーザーが基本操作を提供すると、プログラムは全方位木 DP によって木全体の集約を行う。

理論

木 $T$ に関して、 $T$ の頂点集合 $T’$ と $T$ の $r$ の組 $(r,T’)$ が次の条件をすべて満たすとき、その組をここでは 強クラスター と呼ぶことにする。

いま、 $T$ の強クラスター $(r,T’)$ に、それぞれ対応する値 $f(r,T’)$ が割り当てられているとする。また、この値に対して次のような操作が許されているとする。

このとき、全方位木 DP では木の頂点数を $n$ として、操作回数を $O(n)$ に抑えて、重要な強クラスターについて $f(r,T’)$ の値を得ることができる。

クラス AnyDirectionTreeDP

テンプレート引数

template<
    class S,
    class RakeFunc,
    class CompressFunc
>

これらのテンプレート引数がコンストラクタの引数から推論されることを想定している。

コンストラクタ

AnyDirectionTreeDP(
    const Graph& tree,
    std::vector<S> node,
    RakeFunc _rake,
    CompressFunc _compress
);

nachia::Graph とは?

メインの処理を行う。

getAtVtx

S getAtVtx(int i);

木 $T$ 全体の頂点集合を $T’$ としたときの $f(r,T’)$ の値を返す。

getAtEdge

S getAtEdge(int root, int edge);

$v=\text{root}$ とし、 $w$ を辺 $\text{edge}$ の $2$ つの端点のうち $v$ でないほうとする。

木 $T$ のうち、 $\text{dist}(v,x)\lt\text{dist}(w,x)$ であるような頂点 $x$ の集合を $T’$ としたときの $f(v,T’)$ の値を返す。


TOP PAGE