AOJ 2966 - G トレジャーハンター (Treasure Hunter)

解説の通りこちらを参考にして通しました。
再帰でDFSをしながらナップサックを解き、戻り値として、今いる頂点 $p$ を使用した際の最適解配列 $X_{p0}$ と、使用しなかった際の最適解配列 $X_{p1}$ を返します。
今いる頂点を $p$ とします。子を $a$ とします。

1つめの子に対する再帰
引数で渡された配列 $V$ をそのまま子の引数にします。
戻ってきた値について、
$X_{p0}$ の処理は、それぞれの添え字 $i$ について、 $X_{p0}[i] = max(V[i],X_{a0}[i],X_{a1}[i])$ で更新します。
$X_{p1}$ についての処理は、今いる頂点と $a$ 両方を使用するときは、コスト $c_{pa}$ がかかることに注意し、 $X_{p1}[i] = max(V[i],X_{a1}[i-c_{pa}])$ で更新します。
2つ目以降の子に対する再帰
$X_{p1}$ について考えます。
$X_{p1}$ をまず引数にして再帰します。
そして、先ほどとほぼ同様の処理、具体的には $X_{p1}[i] = max(X_{p1}[i],X_{a1}[i-c_{pa}])$ による更新をします。
$X_{p0}$ について考えると、知りたいのは、 $a$ を根とする部分木についての最適解であるため、 $D$ という配列を用意し、全てを0で初期化して、これを改めて引数として再帰します。
そして、得られた結果について、 $X_{p0}[i] = max(X_{p0}[i],X_{a0}[i],X_{a1}[i])$ で更新します。