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\) 加一即可。