A. 2023
追加方法は x, 1, 1, 1, … でよいです．
B. Two Divisors
単に two largest divisors といって $x$ が含まれない問題文は流石に…．
小さい約数に対して $x/b,x/a$ が与えられると思うと簡単です．$a,b$ は素数 $p,q$ または $p,p^2$ です．
C. Training Before the Olympiad
入力は 0, 1 としてよいです．何らかの値を $2k$ 変えるとその値からできるものすべてが $2k$ 変化するだけだからです．
sum を減らす行為は偶数と奇数で操作することだけです．後手番には常に偶数があるので，奇数の個数に注目すると，おおよそ奇数の個数の $1/3$ 倍くらい和が減ることが分かります．
D. Mathematical Problem
1690000
1060900
1006009
9610000
9060100
9006001
とするとひとつ足りないので 1960000 も入れて完成．
E. Happy Life in University
ほぼ基本的な木DPのような形です．種類数をどう扱うかだけ要検討という感じです．
種類ごとに代表元ひとつだけが数えられるようにします．具体的に最も根に近いものだけを数えることにします．
すると，$c$ を木の辺に沿って移動するときの列 $(diff(v,c))_v$ の変化がいくつかの subtree add で書けます．変化回数のすべての辺に対する sum は $O(N)$ なので，subtree add, subtree max 等のクエリですべてが書けます．
F. Group Division
関節点が存在しないという（制約には書かれていないが問題文に書かれている）条件より st-numbering がとれて，その前半 $n_1$ 頂点と後半 $n_2$ 頂点をとってくればよいです．$O(n_1+n_2)$ 時間で解けます．
乱択した全域木の辺で切るという方法でも AC になったそうです．
G. Optimizations From Chelsu
重心分解して根付き木の根を通るパスに帰着します．根が端点の場合は計算しておきます．
$(depth, gcd) = (l_1,g_1), (l_2,g_2)$ を組み合わせることを考えます．$l_1\leq l_2$ として，$(l_1+l_2)\gcd(g_1,g_2)>l_2g_2$ となる場合だけ調べればよいです．これより $g_2\mid g_1$ だけ調べればよいです．
$g_1=kg_2$ として，適切な範囲を試します．$(l_1+l_2)g_2>l_1g_1$ だけ試せばよいので $k<2l_2$ も仮定できます．
根が端点の場合の答を $S$ として，
- $2l_2g_2>S$ のときだけ計算．$1\leq k\leq 2l_2$ だけ計算．
- 同じ $g_2$ に対しては最大の $l_2$ だけ計算．
のように枝狩りします．これで $O(n\log^2 n)$ になると思います．公式解説（$O(n^{1.5}\log n)$ を主張している）の計算量解析を参考にしました．
- 計算対象となる $(g_2,l_2)$ に対して，根からその頂点までの $l_2$ 個の根以外の頂点に $+1$ する．それらの総和をおさえたい．
- 深さ $L$ の頂点 $(G,L)$ をひとつとってその点に加算が $m$ 回きたとする．ある $g_2\leq G/m$ であるような $(g_2,l_2)$ から加算されたことになる．この $(g_2,l_2)$ は $2l_2g_2>GL$ を満たさなくてはいけないので $2l_2>mL$ が分かる．この頂点の subtree size は $l_2-L$ 以上なので，$(m-2)L/2$ 以上である．
- 同じ深さの頂点の subtree が重複しないことから，深さ $L$ の頂点に対する加算回数を $m_1,m_2,\ldots, m_{cnt}$ として $\sum (m_i-2)L/2\leq n$ が分かる．$\sum (m_i-2)\leq 2n/L$．$\sum m_i\leq 2n/L + 2\times cnt$．
- これを $L$ について足して，総和は $O(n\log n)$．重心分解と合わせて $O(n\log^2n)$．
H2. Matrix Rank (Hard Version)
これは単にほぼ有名問題です．行列を線形写像だと思うと，Ker, Im を固定したうえで計算すればよいです．この固定で $q$ 二項係数がふたつつきます．これに $(r,r)$ full rank matrix の個数をかければよいです．これは線形独立にベクトルをとっていくと考えると簡単な掛け算になります．
