東京海上日動コン2020 D - Knapsack Queries on a tree (700)
最初の考察
$ N=10^{18}と誤読
それぞれのクエリでナップザック問題を解くと$ O(LQ \log N)で$ 10^{11}ほどかかってTLEしそう
最悪ケースだと先祖64個ほどの内16個ほどしか他と共用せず、残りの分は毎クエリでちゃんと計算する必要がありそう
次の考察
$ N=2^{18}であることに気付く
$ \log Nが小さくなったが愚直にやるとTLEしそう
半分全列挙にすると$ O(Q (L + 2^{\frac{\log N}{2}}\log N))でできそう
半分を使って重さ毎に作れる最大の価値を求める
残り半分を使って作れる全パターンに対して上で作った重さ毎の最大の価値を利用して、全体での最大の価値を求める
QLが大きくてTLE
最終的な考察
上半分で重さ毎に作れる最大の価値を求めるようにすると、クエリを越えてこの部分を再利用できる
上半分についてその中で一番下の要素毎に最大価値のパターンを作る
クエリ毎に下半分を使った全パターンを求めて全体の最大の価値を求める
$ O(2^{\log N}L + 2^{\frac{\log N}{2}}Q\log N)で$ 10^8程度になり間に合う