A. Bad Ugly Numbers
999998 のような数で作りました．
B. Maximums
これまでの max が何であるかを持っておけば，それぞれ簡単に決まります．
C. Permutation Partitions
value は単に上位 $k$ 個の和です．数え上げは，上位 $k$ 個のそれぞれの間をどこで区切るかの方法の積です．
D2. Prefix-Suffix Palindrome (Hard version)
prefix, suffix を何文字かずつ対応させたあと，どちらか長い方に回文が余っている．という形になります．ある解があれば，回文パートが中心を固定したときに極大であるような解が作れます．よって，中心を固定したときに極大であるような回文を全探索すればよくて，Manacher などで解けます．
E. Bombs
まずはクエリごとに答えが $x$ 以上であるかという判定問題を解くことを考えます．すると $p$ の値を $0,1$ の $2$ 値だとして $1$ の個数がどうなるかを調べればよいことになります．
$i=1,2,\ldots,n$ 順に答えを求めます．すると答えに単調性があるため，$x$ をスライドさせながら判定を行えばよいです．$x$ をスライドさせることは $p$ の $0,1$ のひとつを反転させることに対応します．
結局，add, chmax の関数合成のセグメント木で点変更を合計 $O(N)$ 回行う形で解けます．
F2. Wise Men (Hard Version)
グラフがあって，長さ $n$ の順列に対して「グラフの辺である・ない」の 01 列を対応させるとき，この列として可能なものを数えるという問題．
包除原理を考えると，数えるべきものは 01 列ではなく *1 列（* のところには 0,1 どちらを入れても良い）となります．
*, 1 の列を決めると，分割数が登場．$n$ の分割 $(a_1,a_2,\ldots)$ が与えられて，点素な頂点数 $a_1,a_2,\ldots, a_m$ のパスのとり方を数えるという問題になります．
予め頂点数ごとのパスの個数のゼータ変換を求めておけば，これは分割ごとに $O(m\cdot 2^n)$ 時間で求められます．（頂点数の和が $n$ であるような分割をとっているので subset convolution ではなく or convolution で十分です．）
これをすべての分割に対してやっても TL に間に合います．
G. Spiderweb Trees
多項式時間にはなりそうでしたが $O(n^4)$ にするところは結構悩みました．
戦略は単純で，普通に木 dp をしながら各頂点では凸多角形を作る dp をするというものです．
点列 $v_0,v_1,\ldots,v_k$ が valid であるかの判定を考えます．作る木は，これらの点が張る steiner tree です．これらが dfs 順に並ぶような dfs 順が存在する（親から見て反時計回りの順に子をたどる）ので，頂点集合は $(v_i,v_{i+1})$ path の和集合になります．
$v_iv_{i+1}$ パス上の点が，辺 $v_iv_{i+1}$ について左側にあるという必要条件があります．これが実は，すべての頂点が凸多角形に含まれるという十分条件にもなります．
そうでないとすると，どこかの辺を突き破って凸多角形の内部から外部へ出てしまうはずで，突き破る辺を $v_iv_{i+1}$ とするとそのようになります．
これさえ分かればあとは自然な木dpになるはずです．
$r$ を根とする部分木の計算では，$r$ を葉とするか否かに分けて計算しました．$r$ を葉としない場合にはどれかのパス $v_iv_{i+1}$ が $r$ を通る必要があるため，$r$ を通ったかのフラグを管理しながら凸多角形を作る dp をします．またパス $v_iv_{i+1}$ を使うときに，「パス上の点の右側にある部分木」での dp の値を掛け算するという要領です．どうせ凸多角形を作る dp に $\Theta(n^3)$ かけるので，毎回パス上の点とその子を全部ループしてもよいです．また steiner tree の生成元が葉になるように，$v_i,v_{i+1}$ が子孫先祖関係にないことなども要求します．
$r$ を葉として採用する場合には，部分木方向のひとつだけを使うので，それを固定すると似たような計算ができます．
