A. Sum in the tree
深さ偶数の頂点について,自身とその子の和が分かっているということになります.それらの和を自身に割り当てるのが最適になります.
B. Nice table
ある行に 3 種の値が並んでいる場所があると,まずそこの列が決まり,すると列について,ab の 2 種がある列と cd の 2 種がある列というようなものが交互に繰り返されることが分かります.
結局,「ab の行,cd の行が交互」「ab の列,cd の列が交互」のうち少なくとも一方を満たす場合しかないことが分かります.
C. Construct a tree
subtree size の和は depth の和と思った方が考えやすいかもしれません.
子の個数の上限と頂点数と根の現在の深さとを決めると,depth sum として可能な範囲が計算できます.子を付つけても良い頂点のうち最も浅いものにつけていく貪欲をします.許容される子の個数が $1$ 個の場合を場合分けすれば $O(\log N)$ 時間で計算できます.
これが出たら,まず最小化問題が解けます.その後,各深さの頂点の個数を決めていきますが,これも上で述べた関数を使いまわして適切な範囲の問題が残るようにしていけば決定できます.
D. Eels
dangerous ではないものを最小化します.
ソートしたときに,$2\sum_{i<j} a_i<a_j$ となる $j$ の個数を $k$ とするとき,$k$ が最小値となります.$k$ を達成するには昇順にマージしていけばよいです.$k$ 以上になってしまうことは,そのような $j$ を境界として $k+1$ グループに分けます.操作のたびにグループ間に辺を張っていくと最終的に連結になるのでが,異なるグループがマージされる瞬間を考えるよいです.
結局 $k$ を求める問題に帰着されます.$a_i$ を $[2^i,2^{i+1})$ の区間に分けて管理すると $a_j$ の候補は区間内の最小値だけに限定できます.これらを全部調べればよいです.
E. Fedya the Potter
まず区間 gcd を列挙します.左端を止めたとき,区間 gcd は約数約数で変化するため,右端は区間 gcd が定数であるような区間 $O(\log A)$ 個に分かれます.これをセグメント木などで求めればよいです.
結局,列 $b$ は run-length encoding された形で求まります.成分が $O(A)$ 子です.
答は二分探索で求めます.すると,$b$ の subarray で sum がいくつ以下であるものを数えよということになります.
左端・右端をどのブロックから取るかですが,sum としきい値の大小関係が非自明な組は $O(|b|)$ 組しかありません.これを尺取りで列挙します.
とるブロックが決まれば,計算すべきはある凸多角形内の格子点の数え上げになり,これは floor_sum で求めることができます.
F. Ж-function
suffix tree をとると,次の問題に帰着されます.
辺重みのある $n$ 頂点の木 $G$ がある.このうち $N$ 頂点には番号 $0, \ldots, N-1$ がついている.クエリ $(a,b)$ に答えよ:$\sum_{a\leq i<b}\min(b-a,\mathrm{depth}(\mathrm{lca}(a,i)))$ を求めよ.
static top tree で解きました.各クラスタでは,頂点 $0, \ldots, N-1$ のうち含むものと,それらの exposed path との lca の組をすべて列挙します.
クラスタのマージが行われる部分で,一方に $a$ が,他方から $i$ があるような $(a,i)$ に対する求値をまとめて行えば,$a\neq i$ であるようなものに対するすべての和が計算できます.また lca がどこにあるかもとれます.
一番難しいパターンでは,静的な点群に対する長方形和のクエリを処理することになります.全体で $O(N\log^2N)$ 時間です.