根付き木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のような畳み込み合成では子のサイズや資源量を別に数える。
問題一覧
- ABC309 E「Family and Insurance」 公式問題組合せ: 最小十分状態からDPを設計する
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: DPの最小十分状態
- ABC409 E「Pair Annihilation」 公式問題
- ABC239 E「Subtree K-th Max」 公式問題
- ABC391 E「Hierarchical Majority Vote」 公式問題
- ABC459 E「Select from Subtrees」 公式問題組合せ: 組合せ係数と対称性で数える
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: 組合せ係数・数え上げ
- ABC378 F「Add One Edge 2」 公式問題
- ABC447 F「Centipede Graph」 公式問題
- ABC397 E「Path Decomposition of a Tree」 公式問題
- ABC394 F「Alkane」 公式問題
- ABC312 G「Avoid Straight Line」 公式問題
- ABC259 F「Select Edges」 公式問題組合せ: 交換論から選択順を導く
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: 貪欲法と交換論
- ABC287 F「Components」 公式問題組合せ: 資源・容量DP
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: 資源軸knapsack DP
- ABC263 F「Tournament」 公式問題
- ABC416 F「Paint Tree 2」 公式問題組合せ: 資源・容量DP
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: 資源軸knapsack DP
- ABC248 G「GCD cost on the tree」 公式問題組合せ: gcd不変量・差分構造
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: gcd不変量・差分構造(gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: gcd不変量・差分構造
- ABC264 Ex「Perfect Binary Tree」 公式問題
- ABC329 G「Delivery on Tree」 公式問題組合せ: ancestor query・LCA
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: ancestor query・LCA
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC246 G「Game on Tree 3」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。主タグ: 単調境界探索 / 補助タグ: 根付き木DP・部分木集約
- ABC269 Ex「Antichain」 公式問題
技能・出典
主題: heavy path上の多項式木DP(heavy child上の漸化式をまとめ、light subtreeのsize総和を利用して木DPの多項式合成を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。) / 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。主タグ: heavy path上の多項式木DP / 補助タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化、再帰分割・分割統治、根付き木DP・部分木集約
- ABC293 Ex「Optimal Path Decomposition」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。主タグ: 単調境界探索 / 補助タグ: 根付き木DP・部分木集約
- ABC298 Ex「Sum of Min of Length」 公式問題
技能・出典
主題: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。主タグ: ancestor query・LCA / 補助タグ: 根付き木DP・部分木集約
- ABC314 F「A Certain Game」 公式問題
技能・出典
主題: DSU merge tree・Kruskal reconstruction tree(成分併合ごとに新しい親nodeを作り、併合時刻・threshold・成分包含を一つのrooted treeへ記録する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: DSU merge tree・Kruskal reconstruction tree / 補助タグ: 寄与の数え上げと順序交換、DSUによる連結成分管理・縮約、法上の四則演算・高速累乗・逆元、根付き木DP・部分木集約
- ABC340 G「Leaf Color」 公式問題
技能・出典
主題: virtual tree・auxiliary tree(対象頂点と必要なLCAだけをEuler順・stackで結び、元の木上pathを保つvirtual treeを構成できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。主タグ: virtual tree・auxiliary tree / 補助タグ: 根付き木DP・部分木集約
- ABC369 G「As far as possible」 公式問題主題: 分離凸・凹の単調限界値選択
技能・出典
主題: 分離凸・凹の単調限界値選択(分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。主タグ: 分離凸・凹の単調限界値選択 / 補助タグ: 根付き木DP・部分木集約
- ABC387 F「Count Arrays」 公式問題
技能・出典
主題: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。 cycle縮約後の木でdp[v][j]=∏_{子u}Σ_{k≤j}dp[u][k]。子ごとにprefix和を作れば、親の値ごとに子の全値を走査する二乗因子が消える。functional graph縮約と木DPを先に履修する。主タグ: 関数グラフのcycle・tree分解 / 補助タグ: DP遷移の集約・高速化、根付き木DP・部分木集約
- ABC435 F「Cat exercise」 公式問題
技能・出典
主題: 大小関係をCartesian treeへ変換する(配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。) / 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: Cartesian treeによる区間極値分解 / 補助タグ: DPの最小十分状態、単調stack・queueによる支配候補の削除、根付き木DP・部分木集約
- ABC438 F「Sum of Mex」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 根付き木DP・部分木集約、ancestor query・LCA
前提・学習成果・出典
習得対象の目安: 水色(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・部分木集約の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。