考えたこと

貪欲は無理そうなので，dpっぽい．
一旦，脳筋のdpを書いてみる．

\text{dp}[i][h][m] = (i番目のモンスターまで見て，\text{HP}がh, \text{MP}がmになる) ?\ true : false

蟻本のP62にもあるように，bool型を持つdpは無駄であることが多い．
試しに，m を値として持つことを考えてみる．すると，HPをhに固定したとき，mは大きいほうがよいことに気づく．したがって，以下のdpを書ける．

\text{dp}[i][h] = (i番目のモンスターまで見て，\text{HP}がhであるときの，\text{MP}の最大値)

O(NH) でよさそう．遷移を詰めると以下の通り．

• 初期状態
  • \text{dp}[0][H] = M．それ以外は，-INF．
• 出力
  • \max_{i} (\exists h, \text{dp}[i][h] \ge 0)
• 遷移
  • i, h の昇順に見る．
  • h \ge A_i なら，\text{chmax}(\text{dp}[i+1][h-A_i], \text{dp}[i][h])．
  • \text{dp}[i][h] \ge B_i なら，\text{chmax}(\text{dp}[i+1][h], \text{dp}[i][h]-B_i)．

提出 (47ms)

https://atcoder.jp/contests/abc410/submissions/68230766

フォローアップ

解説を読むと，bitset高速化を用いて，\text{dp}[i][h][w] を更新できると書いてあったので，実装してみました．
ただ，i についての状態をすべて持つとMLEすることを忘れて１ペナしました．in-placeにして実装し直し，AC．
https://atcoder.jp/contests/abc410/submissions/68242110

また，

\text{dp}[h][w] = (\text{HP} がh, \text{MP} がmのときの討伐数の最大値)．

として解くこともできるみたいです（たしかに！）．

得たもの

• bitset高速化はin-place化して，MLEを回避．
• dp の状態数削減について，他の添字についても考えてみる．

考えたこと

「ビット演算は各ビットごと独立」の典型に則って考えてみる．
問題の総 \text{OR} を，ans とかくことにする．
これを最小化したいので，ans の上位ビットはできるだけ 0 にしたい．
そこで，上位ビットから順番に見ていって初めて 1 にしなければならないとき，それがどんなときか考える．少し考えると，

ans の 最上位ビット b が 1\\ \Longleftrightarrow b ビット目が 0 である辺のみを通る，0 から N-1 への単純パスは存在しない．

がわかる．また，それより下位のビットを決めていくときは，これに加えて，それより上位のビット b で ans_b = 0 が確定している場合，b ビット目が 1 であるような辺は通れない．
まとめると，

ans の b ビット目が 1\\ \Longleftrightarrow b ビット目が 0，かつ，ans_i = 0 (i > b) を満たす i ビット目についても 0 である辺のみを通る，\\0 から N-1 への単純パスは存在しない．

ans の 0 であることが確定しているビット以外は 1 で埋めることにすると，この後半の条件は，以下のように書ける．

ans の b ビット目が 1\\ \Longleftrightarrow ans \| w = ans\ かつ\ w \& 2^b = 0 である辺のみを通る，0 から N-1 への単純パスは存在しない．\\

この条件のもとで，bfsを行い，0 から N-1 へ到達可能かを見ればよい．

提出 (467 ms)

https://atcoder.jp/contests/abc408/submissions/68256456

得たこと

bit反転を行うときに，or や and で頑張っていたが，xor で簡単にできる．

考えたこと

各頂点にいる陽電子は別々に考える必要はないので，x_i 個のかたまりとみる．
まず，葉の頂点にいる陽電子が消滅するにはどうしたらよいかを考えると，どれと対消滅するかはわからないが，必ず葉に接続している辺を，電子・陽電子のどちらかは通ってくる．
ここで，辺に視点を移してみる．
ある辺 e の両側の木にそれぞれ，y 個, z 個の陽電子(符号付き)がいるとすると，これらが消滅するには，これらが辺 e を通って出会わなければならない．
制約より，z = -y であるので，辺 e を通る陽電子/電子は |y| 個となる．
これを全ての辺について足し合わせればよさそう．
与えられた木を，0 を根とする根付き木 T として，辺 e = (u, v) (ただし，u が葉側) について，

\text{dp}[u] = (u とそれより葉側の頂点の，x_i の和).

とすれば，求める答えは，

\sum_{e = (u, v) \in E} {|\text{dp}[u]| * w}

で求められる．\text{dp} は，dfsで簡単に求められる．

提出 (42 ms)

https://atcoder.jp/contests/abc409/submissions/68376642

得たこと

木DPばかり考えていた．詰まったときは視点の変更．