Static Top Treeによる動的木DP
境界頂点つきtree clusterをrake・compressで二分合成し、局所更新後の木DP値を根まで再計算する。
この典型を扱う単元: rake・compressで動的木DPを保つ
検索別名: Static Top Tree、Top Tree、rake-compress tree
未知問からこの典型を見つける手掛かり
- 扱う対象
- cluster
- 境界頂点
- 木
- 木DP
- 使う手掛かり
- compress
- rake
- 辺更新
- 頂点更新
- 保つ不変量
- cluster合成
- 二分木
- 境界頂点
- 局所再計算
- 求めるもの
- 全体の値
- 動的木DP
- 更新後の木全体
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 木モデルと構造
関連する典型
- 根付き木DP・部分木集約: 根付き木DPの合成則をboundary付きclusterの結合へ持ち上げ、局所変更後の再計算を対数個のclusterに限定する。
学習成果と学習単位
境界頂点を持つtree clusterの要約と結合を定義し、局所更新後の木DP値を保てる。
rake・compressで動的木DPを保つで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。