解法
解説の通りこちらを参考にして通しました。
再帰でDFSをしながらナップサックを解き、戻り値として、今いる頂点を使用した際の最適解配列
と、使用しなかった際の最適解配列
を返します。
今いる頂点をとします。子を
とします。
1つめの子に対する再帰
引数で渡された配列をそのまま子の引数にします。
戻ってきた値について、
の処理は、それぞれの添え字
について、
で更新します。
についての処理は、今いる頂点と
両方を使用するときは、コスト
がかかることに注意し、
で更新します。
2つ目以降の子に対する再帰
について考えます。
をまず引数にして再帰します。
そして、先ほどとほぼ同様の処理、具体的にはによる更新をします。
について考えると、知りたいのは、
を根とする部分木についての最適解であるため、
という配列を用意し、全てを0で初期化して、これを改めて引数として再帰します。
そして、得られた結果について、で更新します。
これらの処理が済んだら、について使用する方はお宝の価値を加算して、
を戻り値として返します。