JOI 2009 春合宿 day4 distribution(冊子の配布)
- 問題
- 解き方
木構造で何かしらの最大を求める問題は木dpっぽさを感じたので、この方針で突っ込んだ。
自分の子が持つべき情報は、何冊もらった時にどれだけのやる気を得ることができるかのテーブル。
この情報があれば、普通のdpの遷移と同じようにやれる。
つまり、
dp[v][i] := vを根とする部分木に i 冊配った時のやる気の総和の最大値
と定義する。
dp[v].size() = m として全頂点でdpをすると、遷移的にO(NM^2)になって間に合わないので、二乗の木dpというテクニックを使って高速化。
これは
木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
の解説を参考にするとよい。
- 自分の提出
Submission #21851215 - 2009年 日本情報オリンピック春合宿OJ
