根付き木DP・部分木集約
子部分木の状態をbottom-upに合成し、親へ渡す最小十分なopen/closed状態や要約を設計する。
この典型を扱う単元: 根付き木DP・部分木集約
検索別名: subtree DP、tree DP、根付き木DP
未知問からこの典型を見つける手掛かり
- 扱う対象
- 子状態
- 根付き木
- 部分木
- 使う手掛かり
- bottom-up
- 部分木ごと
- 保つ不変量
- 子の独立性
- 親へのinterface
- 求めるもの
- 木上数え上げ
- 部分木集約
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 木モデルと構造
関連する典型
- small-to-large・DSU on Tree: 子部分木の集合・mapを小さい側から大きい側へmergeする木DPで併用する。
学習成果と学習単位
根付き木で子側の状態を合成し、部分木または木全体の値を求められる。
根付き木DP・部分木集約で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC239 E「Subtree K-th Max」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC394 F「Alkane」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC239 E「Subtree K-th Max」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC246 G「Game on Tree 3」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC248 G「GCD cost on the tree」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC259 F「Select Edges」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC263 F「Tournament」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC264 Ex「Perfect Binary Tree」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC269 Ex「Antichain」 公式問題主題: heavy path上の多項式木DP / 補助タグ
技能・出典
主タグ: heavy path上の多項式木DP / 補助タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化、再帰分割・分割統治、根付き木DP・部分木集約
- ABC287 F「Components」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC293 Ex「Optimal Path Decomposition」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC298 Ex「Sum of Min of Length」 公式問題主題: ancestor query・LCA / 補助タグ
- ABC309 E「Family and Insurance」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC312 G「Avoid Straight Line」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC314 F「A Certain Game」 公式問題主題: DSU merge tree・Kruskal reconstruction tree / 補助タグ
- ABC329 G「Delivery on Tree」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC340 G「Leaf Color」 公式問題主題: virtual tree・auxiliary tree / 補助タグ
- ABC369 G「As far as possible」 公式問題主題: 分離凸・凹の単調限界値選択 / 補助タグ
- ABC378 F「Add One Edge 2」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC387 F「Count Arrays」 公式問題主題: 関数グラフのcycle・tree分解 / 補助タグ
- ABC391 E「Hierarchical Majority Vote」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC394 F「Alkane」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC397 E「Path Decomposition of a Tree」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC409 E「Pair Annihilation」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC416 F「Paint Tree 2」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC435 F「Cat exercise」 公式問題主題: 大小関係をCartesian treeへ変換する / 補助タグ
技能・出典
主タグ: Cartesian treeによる区間極値分解 / 補助タグ: DPの最小十分状態、単調stack・queueによる支配候補の削除、根付き木DP・部分木集約
- ABC438 F「Sum of Mex」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC447 F「Centipede Graph」 公式問題主題: 根付き木DP・部分木集約 / 主タグ
- ABC459 E「Select from Subtrees」 公式問題主題: 根付き木DP・部分木集約 / 主タグ