A. Linova and Kingdom
各頂点を選ぶ価値を次のように定めます：$\mathrm{value}[v]:=\mathrm{depth}[v]-\mathrm{subtreesize}[v] + 1$.
最適解において子側から詰まった形になるため，value の総和が価値になります．value の総和を最大化すると，自動的に子側から詰まった形になっているのでそれでよいです．
B. Xenia and Colorful Gems
$3$ 色の順を決めて解きます（$6$ 回解く）．$2$ 色目を決めると，他の色はそれ以下，それ以上での最寄りとして最適化できます．
C. Kaavi and Magic Spell
$T$ を，後ろに ‘?’ を補って長さ $n$ にしておきます．
すると，操作の途中状態はすべて $T[l:r]$ のところを作っているという形にかけて，あとは簡単な区間 dp でできます．
D. Yui and Mahjong Set
個人的にはまず $n=4$ から結構非自明でした．
とりあえず返答に応じて戦略を変える可能性は破棄して，質問列を固定する方針にします．
これで一意に決まるかを愚直を書いて調べました．
結局，$0, 1, 2, \ldots, n-3, n-2, 0$ という戦略が上手くいきそうだったのでこれを採用しました．一意に決まるかどうかは証明していないのですが，たぶん手前からちゃんと場合分けしていけば，一時的に複数通りあっても数項先まで読めば決まっていくのだと思います．この予想のもと，実装は適当な rollback dfs で ok です．
E2. Chiori and Doll Picking (hard version)
生成される要素の重複を除けば，次の形です：$\mathbb{F}_2^{53}$ の部分空間の基底が与えられる．ベクトル空間の要素を popcnt で分類せよ．
$2$ つの解法を使い分けます．
【解法 1】
全列挙．ベクトル空間の次元が $d$ 次元のとき $O(2^d)$ 時間で解けます．gray code の要領で全列挙しました．
【解法 2】
$m$ 次元空間のうち $d$ 次元部分ベクトル空間が与えられているとき，$O(m\cdot 2^{m-d})$ 時間で解けます．
基底を行階段形にして，さらに列の交換も適当に行うことで，次の形になります．
– $a_i=2^{m-1-i}+b_i$ ($0\leq i<d$, $0\leq b_i<2^{m-d}$).
$b_i$ を使う・使わないの $2$ 択を考えて，$[0,2^{m-d})$ での xor 畳み込みを使います．$b_i$ を使った個数を表す変数 $t$ を用意して，$(1+tx^{b_i})$ を畳み込むというようにします．すると，各点に $1\pm t$ のうち適切な法をかける形になります．
どのような popcnt にどのような $(1+t)^i(1-t)^{d-1}$ がいくつ足されているかなどを経由して答を計算できます．
F. Journey
場合分けの方針として
- $2$ つのパスの LCA が異なる場合
- $2$ つのパスの LCA が一致する場合
とします．前者について，LCA が深い方のパスからもう一方のパスを数えることを考えると，適当な矩形クエリの形になって数えられます．
後者について考えます．登場するすべてのパスの端点をとって圧縮木を作ることで，$n$ 頂点の根付き木ですべてのパスが根を通る場合を $O(n)$ 時間程度で解ければよいということにします．
後者の場合を考えます．パスは根から $2$ 方向以下に伸びます．このうち $1$ 方向だけが共通の場合をまず計算します．これは，深さ $k$ のところが一致という条件になって計算できます．あとは，パスが根から同じ $2$ 方向に伸びている場合が解ければよいです．
これも $2$ 方向を取り出して，やっぱり木を圧縮します．根の次数が $2$ ですべてのパスが両方向に伸びている場合に帰着できます．方向 1 を dfs しながら，マージテクを使って方向 1 側のパス長ごとに計算します．気合実装．
