StaticTopTreeDP

クラス · Static Top Tree（木を rake / compress の二分木へ分解する）

template <tree_dp TreeDP>
struct StaticTopTreeDP;

概要

Static Top Tree 上の木DP（頂点値の点更新に対応）

木 DP の演算を StaticTopTree の各ノードで評価し、根の値として木全体の集約値を保つ。頂点 $u$ の値を変えたら dp を書き換えて update(u) を呼ぶと、$u$ から根までの $O(\log n)$ 個のノードだけが再計算される。

使い方は StaticTopTreeDP<DP> d(g, root, DP{...}); で構築し、頂点 $u$ の値を変えるときは d.dp の頂点データを書き換えて d.update(u) を呼び、d.get() で木全体の集約値を読む。同じ形状で別の DP を走らせたいときは StaticTopTree を先に作って共有できる。

テンプレートパラメータ

名前	説明
`TreeDP`	木DPの演算（`tree_dp` を満たすこと）

計算量

構築と全再計算は $O(n)$、点更新は $O(\log n)$、集約値の取得は $O(1)$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空のDPオブジェクトを構築する (2) 木gを根rで分解し、全ノードのDP値を計算する (3) 構築済みのStatic Top Tree上で全DP値を計算する	(1) $O(1)$ (2) $O(n)$ (3) $O(n)$

メンバ関数

名前	説明	計算量
`update_all`	全ノードのDP値を再計算する	$O(n)$
`update`	頂点uの値を `dp.vertex(u)` から取り直し、根までのノードを更新する	$O(\log n)$
`get`	木全体の集約値を返す	$O(1)$

メンバ型

名前	説明	計算量
`Path`	重パス上の集約値型	型エイリアスのため実行時コストなし
`Light`	軽辺クラスタの集約値型	型エイリアスのため実行時コストなし

メンバ変数

名前	説明	計算量
`stt`	DPの土台となるStatic Top Tree	1 ノードの参照は $O(1)$
`dp`	木DPの演算オブジェクト。頂点値の変更はこれを書き換えて `update` を呼ぶ	参照は $O(1)$

メンバの詳細

(constructor)

// (1)
StaticTopTreeDP() = default;

// (2)
template <graph_type G>
explicit StaticTopTreeDP(const G &g, int r = 0, const TreeDP &_dp = TreeDP());

// (3)
explicit StaticTopTreeDP(StaticTopTree _stt, const TreeDP &_dp = TreeDP());

(1) 空のDPオブジェクトを構築する

計算量: $O(1)$

(2) 木gを根rで分解し、全ノードのDP値を計算する

計算量: $O(n)$

(3) 構築済みのStatic Top Tree上で全DP値を計算する

計算量: $O(n)$