A. Lawn Mower
$k=\lfloor n/w\rfloor$ とすると，幅 $w$ の区間を $k$ 個 disjoint にとれるので，残すものが $k$ 個以上必要です．1-based でインデックスが w の倍数のところを残すとこれを達成できます．
B. Offshores
$2$ 回以上動かすものはないとしてよいです．ゴールに向かって $2$ 回移動した辺があったときに，$1$ 回ずつキャンセルして直通させるように変換する．という変形で証明できます．
C. Secret message
約数を昇順にチェックしていけばよいです．
D. Table Cut
各行からいくつ残すかという列 $(a_1,a_2,\ldots,a_n)$ を考えます．これを，$(0,0,\ldots,0)$ から $(m,m,\ldots,m)$ に向かって変化させていきます．
列 $a$ には単調増加ですという制約があります．まだ $m$ 個未満であるような最後のインデックスにインクリメント，という操作を繰り返せばこのような変化ができます．
この仮定で左側にある $1$ の個数は $0,1$ 個のどちらか増えるという変化しかしないので，どこかで目的の個数になっています．
E. The Turtle Strikes Back
flip するマスごとにすべて答を求めます．
各 $k$ に対して，$i+j=k$ であるような $(i,j)$ に対する答をまとめて求めます．どのような経路についてもこのような $(i,j)$ はちょうど $1$ つ経路に含まれることに注意します．
まず，手前，後ろ側から dp することで，各マスを通る場合の最大値を求めておきます．
$i+j=k$ となるマスが $n$ 個あるとして，$(i,j)$ を flip したとします．
$(i,j)$ を通らない場合は，「その他 $n-1$ 個の max」として求まります．
$(i,j)$ を通る場合は，そのマスの寄与が変化するだけです．
F2. Again Trees… (hard version)
結局，$B$ の span するベクトル空間 $V$ を求めてしまう方が実装が楽になりました．
ある $v$ の subtree において，切り離された頂点集合の総 XOR は，$V$ に入る $2^d$ 個しかないのがポイントです．これで，$2^d$ 状態の dp になって，F1 は解けます．マージが $(2^d)^2$ など．
- dp マージは XOR convolution の形をしています．
- $v$ の subtree における $A_v$ の和を $a$ とするとき，$a\oplus b_k$ に対応する部分の dp テーブルの値の和を求めて，その値を dp テーブルの $a$ の位置に加算．という処理が必要になります．
後者の処理について，取得は $b_k$ に対応する要素を $1$ とした列 $B$ としたとき，dp テーブルと $B$ を XOR convolution して $a$ に対応する位置を読む．という形になります．
以上を踏まえて，何もかもを dp ではなく，Hadamard(dp) の形で保持するということを考えます．
XOR convolution は単に各点積になります．
$B$ ではなくその Hadamard 変換を求めておけば，$a$ に対応する数え上げの取得も $O(2^d)$ 時間です．各点積の値を $popcnt(a \& i)$ の偶奇に応じた重みで足してくるという形になります．
$a$ に対応する値を足しこむのも，$popcnt(a \& i)$ の偶奇に応じた重みで値を足すだけです．
空間が足りるか確信がなかったので，$O(\log N)$ 個の空間でやりくりしました．通った light edge の個数を level として，level 番目のテーブルを使うというようにすればよいです．
