主要补充官方题解的 T2 和 T3。

A

***题，不算复杂度差不多得了，显然交换 $SS$S / $TT$T 的选出区间中的任意位置不影响答案，于是前缀和即可。

B

清新题，只不过我的确不会...部分分设置不太合理。

你考虑用 $O\left(h^2{w}^2\right)O(h\; ^\; 2\; w\; ^\; 2)$O(h2w2) 的时间钦定两个点 $(x_1,y_1),(x_2,y_2)(x\_1,\; y\_1),\; (x\_2,\; y\_2)$(x1​,y1​),(x2​,y2​) 研究线段，同时令 $a=\mid x_1-x_2\mid ,b=\mid y_1-y_2\mid a\; =\; |x\_1\; -\; x\_2|,\; b\; =\; |y\_1\; -\; y\_2|$a=∣x1​−x2​∣,b=∣y1​−y2​∣。如果你做过 仪仗队 那么很容易想到中间一共有 $\gcd (a,b)\backslash gcd(a,\; b)$gcd(a,b) 个点，把这些点当作盒子，把它们拍到序列上，则我们有 $\gcd (a,b)-1\backslash gcd(a,\; b)\; -\; 1$gcd(a,b)−1 个盒子，$n-2n\; -\; 2$n−2 个点（钦定端点必选）。如果我们令 $k=\lfloor \frac{d}{dis\left(\right(0,0),(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\left)\right)}\rfloor k=\backslash lfloor\backslash frac\{d\}\{\{\backslash rm\; dis\}((0,\; 0),\; (\backslash frac\{a\}\{\backslash gcd(a,\; b)\},\; \backslash frac\{b\}\{\backslash gcd(a,\; b)\}))\}\backslash rfloor$k=⌊dis((0,0),(gcd(a,b)a​,gcd(a,b)b​))d​⌋，则每个球放进的盒子编号差需 $⩾k\backslash geqslant\; k$⩾k。

赋予组合意义，则每个球存在「体积」的概念，且该「体积」为 $k-1k\; -\; 1$k−1，考虑将其压缩， 那么答案式子就出来了 $\left(\frac{\gcd (a,b)-1-(k-1)-(n-2)(k-1)}{n-2}\right)\backslash binom\{\backslash gcd(a,\; b)\; -\; 1\; -\; (k\; -\; 1)\; -\; (n\; -\; 2)(k\; -\; 1)\}\{n\; -\; 2\}$(n−2gcd(a,b)−1−(k−1)−(n−2)(k−1)​)，那个 $k-1k\; -\; 1$k−1 是右端点已经必选了，所以少了 $k-1k\; -\; 1$k−1 个盒子。

考虑优化，注意答案取决于 $aa$a 和 $bb$b，可以乘个系数来优化。

C

清新题，部分分非常暗示。

有个显然的 observation 是一个结点一定从子树中至多选两个未被选择的结点转移，那么就可以直接可并堆启发式合并什么的来转移。

主要问题是为什么不是儿子中选呢？你考虑一个结点 $xx$x，其父亲 $pre\left(x\right)pre(x)$pre(x) 只有 $xx$x 一个儿子，而 $xx$x 有三个儿子，并且 $xx$x 把其中两个儿子选完了，那么 $pre\left(x\right)pre(x)$pre(x) 一定是从 $xx$x 的另一个儿子转移上来，所以必须把子树考虑完。

D

你出你🐎的 BM 呢😅😅。