A. DBMB and the Array
総和に $x$ を加算していって $s$ になるかどうかです．
B. Reverse a Permutation
reverse は長さ $2$ 以上の区間に行うとして，操作は $1$ 回以下としてよいです．
reverse されずに残る prefix 部分を考えます．
先頭が $N$ でない場合，それを先頭に持ってくるように reverse する方法が唯一で，それが解です．
そうでないとき，先頭は reverse 対象にしない方が良いので，先頭を無視して解けばよいです．
C. Replace and Sum
$a_i$ の子が $a_{i+1}$, $b_i$ であるような根付き木を考えると，親の値を子の値に置き換えられるということです．
置き換えて増えない操作は行わないとしてよく，増える操作はすべて行うとしてよいです．子側から順にこれを行います．
D. Monster Game
クリアするレベル数を固定すると，sword をいくつ使うべきかが決まり，事前にソートしておけば必要な $x$ が分かります．
E. Product Queries
同じ要素を何度でも使える設定なので，入力は unique してよいです．
$x$ を作るための最小コストを $\mathrm{dp}[x]$ として，$a_i$ を追加するごとに dp テーブル全体を更新します．
この更新が $O(N/a_i)$ 時間で行えることから，すべての $a_i$ を考慮しても調和級数時間 $O(N\log N)$ 時間です．
F. Pizza Delivery
$x$ 座標昇順に処理します．各 $x$ 座標では，目標地点は $y$ 座標最小のものと最大のものの $2$ つであるとしてよく，そのどちらを先にとるかの $2$ 択を処理します．これで dp すればよいです．
G. Paths in a Tree
次を繰り返します：木の頂点のうちで未消去の $2$ 頂点であって，その $2$ 点を結ぶパス上に他の未消去の点がないものをとる．この $2$ 頂点に質問し，削除する．
質問ではじめて “1” がかえってきたタイミングで，その $2$ 頂点のどちらかが解ということになり，最後に $(u,u)$ 型の質問をすれば特定できます．
$2$ 点組への分割は bottom up な木 dp でマッチさせていくことで作れます．
H. Remove the Grail Tree
頂点はタイプ $0,1$ の $2$ 種類とします．次の必要条件があります．
- タイプ $0$ の頂点の近傍にタイプ $1$ の頂点が存在する．
- タイプ $1$ の頂点だけからなる誘導部分グラフの連結成分の大きさは奇数である．
後者の条件が分かりにくいですが，「タイプ $1$ 同士の点を結ぶ辺」が操作によって偶数本ずつ消えることから，連結成分ごとに辺が偶数個，したがって頂点は奇数個ということになります．
これらは十分条件にもなります．必要条件のもと，必要条件を保ったまま消去を行えることを示せばよいです．タイプ $0$ の頂点で消去可能なものがあれば消去し，そうでない場合には消去可能なタイプ $1$ の頂点のうちで topological 順で一番後ろにあるものをとる．という戦略で目標達成できます．
上のルールで消去可能な頂点があることは，奇数頂点の木には偶数次数の頂点が存在することから分かります．消去で必要条件が壊れないことを確認します．タイプ $0$ の頂点を消す方は簡単です．
タイプ $1$ の頂点の削除について，それが行われるのはタイプ $0$ の頂点はすべて削除不可能であるときです．ここからタイプ $1$ の頂点の削除によってタイプ $0$ の頂点での必要条件が壊れないことが分かります．
topological 順に最大の頂点を選んでいることから，子孫の次数はすべて奇数だったということになります．ここから subtree size がすべて奇数であることが分かり，タイプ $1$ の頂点についても必要条件が維持できることが分かります．
