date: 2020-07-18 12:00~17:00

2020牛客暑期多校训练营（第四场）

题目大意：给个树，要你给这个树的 $K$ 个节点打个标记，每个点算一下到祖先中最近的被标记的点的距离（没有就是无穷大），取最大值作为费用。问你最小费用是多少。对每个 $K \in [1, n]$ 都求一下。

题解：

考虑已经知道最后的费用是 $h$，想想有没有办法尽可能少地去标节点。会发现标节点的过程就是切子树的过程。

想一下从根开始，切掉所有距离为 $h$ 的，嗯，不对。那就只能从最深的叶子开始，搞掉第 $h$ 个祖先，直到搞完。这样贪心正确性比较明显，因为只要有一个最优的方案，你总有办法调整成这样贪心构造出来的样子。

然后我们队，傻兮兮地在维护叶子的情况，需要用 set 来维护 DFS 顺序的叶子；每次切出来一个子树相当于切走了一段区间；然后如果弄出来一个新的叶子，又得加回去。为了能快速地初始化，对于没有并过的叶子还得单独弄成一类特殊的区间。做法诡异极了。

那么正常的做法，考虑一下被切掉的子树，那肯定也就是 DFS 序上的一段区间的所有节点，既然切走了，全部赋值成 0 就好；需要维护的是区间最大值，也就是最深的节点，那也必然是叶子。初始化的话，你可以在标记区间赋值成某个特殊值时，就将该线段树节点的信息恢复成初始的情况，就没了。

签到题。

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

补补补，补个啥啊补

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：