本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-23 14:11:39

A

容易注意到，将 $a$ 升序排序后，相同值作为一整块，那么每一块选择自己整块加上前面块的其中一个元素，这样是最优的。

最后只有最小值不能被删除。

B

容易注意到，最多选择一个大于 $0$ 的元素。

另外，如果选择的最大元素小于等于 $0$，那么所有非正数都可以选择。

现在只需要枚举哪个元素是唯一的正数（当然也可以没有正数）

C

考虑子树选完了，自己该怎么选。

（不一定）容易注意到，只有 $l_u,r_u$ 是可能选择的。

D

考虑 $f(n)$ 代表 $n$ 个点的答案。

考虑第一个点与哪个数匹配，设其为 $r$。

容易注意到，除了在 $[1,r]$ 里面的，所有线段长度都必须等于 $r$ 。

另外，比 $[1,r]$ 长度小的线段只能在 $[n-r+1,r]$ 内部。

容易得到 $[n-r+1,r]$ 不为 $0$ 对应的 $r$ 是一个区间。

另外，另一个结论：

$ 轴有 $n$ 个不同的端点，从左到右编号从 $1$ 到 $n$，$n$ 是偶数。

假设一个整数 $d$，那么两个端点可以配对当且仅当其编号差为 $d$。

一个 $d$ 是好的当且仅当所有端点都可以被配对。

结论：$d$ 是好的当且仅当 $(2d-2) | n$。