典型タグ

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に限定する。

学習成果と学習単位

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。