木上で bit DP する感じ
問題概要
頂点数 
の根付き木が与えられる。各頂点 
には重み 
が付されている。
この根付き木はタスクの依存関係を表している。各頂点に対して、対応するタスクの「実行」と「削除」ができる。
- 頂点 のタスクを実行すると、ディスクに実行結果が記録されて、ディスク容量 (初期値は 0) に が加算される。
- 頂点 のタスクを削除すると、ディスクの実行結果が消去されて、ディスク容量は が減算される。
ただし、頂点 のタスクを実行するためには、 のすべての子頂点についてタスクが「実行」済み、かつ、「削除」前であることが必要である。
目的は、根頂点に対応するタスクを「実行」することである。その状態を達成するまでの過程の、ディスク容量の最大値をスコアとする。
スコアの最小値を求めよ。
制約
解法
次の bit DP で解ける。
dp[S] ← 実行済みのタスク集合が 
の状態に至るまでの最大瞬間ディスク消費量
計算量は 
となる。
コード
提出したコード
