发现终于最讨厌的还是和自己的相同的人的样子。

§ A

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

§ B

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

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

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

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

§ C

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

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

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

§ D

你出你🐎的 BM 呢😅😅。