Good Bye 2023 | maspyのHP

すると， $c$ を木の辺に沿って移動するときの列 $(d i f f (v, c))_{v}$ の変化がいくつかの subtree add で書けます．変化回数のすべての辺に対する sum は $O (N)$ なので，subtree add, subtree max 等のクエリですべてが書けます．

https://codeforces.com/contest/1916/submission/239669762

F. Group Division

関節点が存在しないという（制約には書かれていないが問題文に書かれている）条件より st-numbering がとれて，その前半 $n_{1}$ 頂点と後半 $n_{2}$ 頂点をとってくればよいです． $O (n_{1} + n_{2})$ 時間で解けます．

乱択した全域木の辺で切るという方法でも AC になったそうです．

https://codeforces.com/contest/1916/submission/239831630

G. Optimizations From Chelsu

重心分解して根付き木の根を通るパスに帰着します．根が端点の場合は計算しておきます．

$(d e p t h, g c d) = (l_{1}, g_{1}), (l_{2}, g_{2})$ を組み合わせることを考えます． $l_{1} ≦ l_{2}$ として， $(l_{1} + l_{2}) \gcd (g_{1}, g_{2}) > l_{2} g_{2}$ となる場合だけ調べればよいです．これより $g_{2} ∣ g_{1}$ だけ調べればよいです．

$g_{1} = k g_{2}$ として，適切な範囲を試します． $(l_{1} + l_{2}) g_{2} > l_{1} g_{1}$ だけ試せばよいので $k < 2 l_{2}$ も仮定できます．

根が端点の場合の答を $S$ として，

$2 l_{2} g_{2} > S$ のときだけ計算． $1 ≦ k ≦ 2 l_{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} ≦ G / m$ であるような $(g_{2}, l_{2})$ から加算されたことになる．この $(g_{2}, l_{2})$ は $2 l_{2} g_{2} > G L$ を満たさなくてはいけないので $2 l_{2} > m L$ が分かる．この頂点の subtree size は $l_{2} - L$ 以上なので， $(m - 2) L / 2$ 以上である．
同じ深さの頂点の subtree が重複しないことから，深さ $L$ の頂点に対する加算回数を $m_{1}, m_{2}, \dots, m_{c n t}$ として $\sum (m_{i} - 2) L / 2 ≦ n$ が分かる． $\sum (m_{i} - 2) ≦ 2 n / L$ ． $\sum m_{i} ≦ 2 n / L + 2 \times c n t$ ．
これを $L$ について足して，総和は $O (n \log n)$ ．重心分解と合わせて $O (n \log^{2} n)$ ．

https://codeforces.com/contest/1916/submission/311603791

H2. Matrix Rank (Hard Version)

これは単にほぼ有名問題です．行列を線形写像だと思うと，Ker, Im を固定したうえで計算すればよいです．この固定で $q$ 二項係数がふたつつきます．これに $(r, r)$ full rank matrix の個数をかければよいです．これは線形独立にベクトルをとっていくと考えると簡単な掛け算になります．

https://codeforces.com/contest/1916/submission/239700130