根付き木DP・部分木集約

概要

子部分木の状態をbottom-upに合成し、親へ渡す最小十分なopen/closed状態や要約を設計する。

考え方

根を決めて子を先に処理し、親で子の答えをまとめる。親から見える情報だけを状態に残すと、部分木の詳細を忘れて合成できる。

例えば木の独立頂点集合数では、dp0[v]をvを選ばない個数、dp1[v]を選ぶ個数とする。葉では両方1。子cを順に合成し、 dp0[v]=∏_c(dp0[c]+dp1[c])、dp1[v]=∏_c dp0[c] とする。vを選ぶと隣接する子を選べず、選ばないなら子の二状態が許される。子部分木同士には辺がないため、その選択は独立に掛けられる。根の和が全体数となる。

これは「根を選ぶか」だけを親へ渡せば、今後の可否が決まる例である。親から伸びるpathを一本開く必要がある問題ならopen/closed状態を追加し、何本まで同時に親へ接続できるかを子併合で制御する。初期値は空の子集合の単位元から始め、子の完了順に処理する。

成立条件と計算量

各辺を一回ずつ処理し、定数状態・定数合成ならO(N)。子部分木の選択を独立に掛けられる条件を示す。knapsackのような畳み込み合成では子のサイズや資源量を別に数える。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。子部分木の独立性と親へ渡す状態を定め、bottom-upに合成する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 木DP・集約・rerooting。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-rooted-tree-aggregation

根付き木DP・部分木集約

習得する技能

  • 根付き木で子側の状態を合成し、部分木または木全体の値を求められる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 最小十分状態からDPを設計する。

このUnitを直接前提とする単元: 資源DPを引数で渡すHLRecDP、heavy path上の多項式木DP、rerooting・全方位木DP、rake・compressで動的木DPを保つ。

DPの最小十分状態で得た考え方と実装を再利用し、根付き木DP・部分木集約の発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 根付き木DP・部分木集約の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠