東京海上日動 プログラミングコンテスト2020 D - Knapsack Queries on a tree (700)

問題：D - Knapsack Queries on a tree

解答：Submission #14401193 - Tokio Marine & Nichido Fire Insurance Programming Contest 2020
(yosupoさんのほぼ丸写し…)

解法：愚直にやると18 * LのナップサックをQ回やることになり、間に合わない。途中まで前計算しておき、残りは全探索するような方法を考える。

2⁹ = 512くらいまでは全ての頂点列に関して前もってdp[v][l]：根から頂点vまで見ていて、使っている重さがl以下の場合の価値の最大値、というDPを計算しておく。これは512 * 10 ^ 5 ≒ 5.0 * 10 ^ 7であり、ぎりぎり間に合う。

クエリで頂点が与えられたら、親にどんどんさかのぼってゆき、dp部分に当たるまでは全探索候補として配列に重さを格納してゆく。dp部分に当たった時の頂点をpとすると、全探索で重さswと価値svの組み合わせに対し、sv + dp[p][l - sw] の最大値が答え。