問題

解法

この解法は木上のナップサック問題 #アルゴリズム - Qiita の「応用」で言及されているものと全く同じだと思います。↓でご指摘いただきました。

参考文献の応用のところに同じことが言及されていませんか？詳細は書かれてないので記事自体は価値があると思います
— 熨斗袋 (@noshi91) 2024年5月24日

まず各街 $i$ について

で定まる荷物が与えられれれて、

という制約条件のもと、採用した荷物の価値の合計の最大値を計算する問題です。

以降ナップサック問題の「解配列」といえば、$M / 2$ 以下の全ての非負整数 $i$ について、重量の合計が $i$ 丁度であるという制約のもと価値の最大値（解なしならば $-\infty$）を格納するものを指します。

次の仕様を持つ関数 $\mathtt{dfs}(x, \mathtt{dp})$ を構成しましょう。この関数に $\mathtt{dfs}(0, [0, -\infty, -\infty, \dots])$ を渡すとほしかった解配列が手に入ります。

入力
- 木の節点 $x$
- もとの問題に更に次の制約を加えたナップサック問題の解配列 $\mathtt{dp}$
  - pre-order において $x$ より前の節点に対応する荷物しか使ってはいけない
  - $x$ の祖先の荷物は全て使わなければならない
出力
- もとの問題に更に次の制約を加えたナップサック問題の解配列
  - post-order において $x$ と同じかそれより前の節点に対応する荷物しか使ってはいけない
  - $x$ の祖先の荷物は全て使わなければならない

この関数は次のように再帰的に実装できます。

公式解説、kmjp さんの解説、mayuko_ さんの解説、はまやんはまやんさんの解説（全て参考文献にリンクあり）はどれも、各節点で解配列のマージ（min-plus convolution）を行っていて、$Θ(nm ^ 2)$ 時間かかるので、この記事の解法の方のほうがより高速なはずです。