rerooting・全方位木DP
辺の両側情報とprefix/suffix合成を用いて、全ての根に対する木DP値を線形または準線形時間で得る。
この典型を扱う単元: rerooting・全方位木DP
検索別名: all-direction tree DP、rerooting DP、全方位木DP
未知問からこの典型を見つける手掛かり
- 扱う対象
- 木
- 根
- 辺の両側
- 使う手掛かり
- 全頂点を根
- 根を移す
- 保つ不変量
- 親側情報
- 除外合成
- 求めるもの
- 全根の答え
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 木モデルと構造
関連する典型
学習成果と学習単位
子側と親側の寄与の差し替えを定義し、各頂点を根とした答えを求められる。
rerooting・全方位木DPで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。