2024
在我的深刻思考下，我决定先开xtq的杂题选讲，我能归来吗？
杂题选讲 by xtq
unknown
给定一棵带权树和一个 \(k\)，选 \(k\) 个点标记，使得对于每个点（可以不是标记点）到最近的标记点的距离的最大值最小。\(n \leq 10^5\)。
先二分答案。考虑怎么 \(check\)。以下用“放”表示标记，\(mid\) 是二分的答案。
记 \(d_x\) 表示 \(x\) 的子树内至少放 \(d_x\) 个能使得我再在 \(x\) 处再放一个就能让子树全满足，\(f_x\) 表示再满足 \(d_x\) 最小的前提下 \(x\) 和它子树内最近的标记点的距离最小是多少（这里的地位是先让 \(d_x\) 最小然后再让 \(f_x\) 最小），\(g_x\) 表示如果 \(f_x\) 寄了（\(>mid\) 了）那么对于那些假如只标记那 \(d_x\) 点就无法满足的点中最深的那个点距离 \(x\) 是多少。
考虑如何合并子树。
首先对于 \(d_x\) 那些 \(d_{son}\) 是最基础的得加上，这个就是简单求和。
然后对于 \(f_{son}\) 考虑如果把这个儿子连向 \(x\) 的那个边加进来以后是否依旧 \(\leq mid\)，如果是那么更新一下 \(f_x\)。否则的话如果当前的 \(f_{son}+w\) 全都 \(>mid\)，那么就要更新变成 \(g_x=0\)，\(f_x\) 照常更新取 \(min\)。
接下来是 \(g\)，那么这个 \(g\) 就是我们要满足的，那么子树内显然是不行了，那么肯定是子树外的标记点覆盖它，考虑肯定是另一棵子树内的一个标记点转移过来，我们肯定希望这个标记点到 \(x\) 的距离最小（因为你考虑这个 \(son'\) 子树内的标记点到那个不满足的 \(g_son\) 的距离是\(f_{son'}+w_{son'}+g_{son}+w_{son}\)），那么你就看一下 \(f_{son'}+w_{son'}+g_{son}+w_{son}\) 这个东西是不是 \(\leq mid\) 的即可，这下就没有影响，反正都解决了。
然后如果不能覆盖到，也就是 \(f_{son'}+w_{son'}+g_{son}+w_{son}>mid\)，此时如果 \(g_{son}+w_{son} \leq mid\)，那么显然在 \(x\) 再放一个就完了，那么你更新一下 \(g_x\) 的值就行（用 \(g_{son}+w_{son}\)）。如果 \(g_{son}+w_{son}>mid\)，那么在 \(u\) 放也会寄。我们设 \(g_{son}\) 的那个最深的点是 \(p\)，此时就得在 \(p-x\) 的路径上选一个点使得能覆盖到 \(p\) 并且距离 \(x\) 最近的点，这个也是好维护的，维护以后更新一下新的 \(f_x\) 并且把 \(d_x\) 加一即可。