自动搬运

查看原文

来自洛谷，原作者为

	Wuyanru NOI2025 rp++ 喵~ | 不拿10级勾不改签名 | 我猜我是没机会改签名了

搬运于2025-08-24 22:53:38，当前版本为作者最后更新于2023-12-25 01:34:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

开场不到 2h 过了这题，虽然复杂度比正解大点，但是没有关系。

好像是这次铂金组的最难题？但是我不会这次的 T3 啊。

题目链接。

题意

现在有一棵 $n$ 个点的树，每一个节点上都有一头牛。

这群牛感染了一种病毒，每一天，若一头未被感染的牛与一头已被感染的牛相邻，这头牛下一天就会被感染。

现在告诉你 $d$ 天以后哪些牛被感染了，求第 $0$ 天时最少有几头牛被感染，或报告无解。

$q$ 组询问，所有询问只有时间 $d$ 不同。

$2\le n\le 10^5$。

$0\le d\le n$。

$1\le q\le 20$。

题解

发现 $q$ 很小，所以我们只需要对于每一组询问单独考虑就好，对于每一组询问，我们这样求解：

首先我们对于每一个点 $i$，求出 $tim_i$ 表示所有最终未被感染的牛中，与 $i$ 最近的距离是多少。

那么我们就知道，只有 $tim_i\ge d$ 的点 $i$ 初始才有可能是感染的。

所以我们现在的问题是，在所有 $tim_i\ge d$ 的牛中选出尽可能少的点，使他们恰好可以“覆盖”所有最终被感染的点。

发现整个问题不是很好 dp，所以我们考虑贪心。

考虑如下的贪心过程：

1. 找到当前未被覆盖的点中，深度最大的那个，记作点 $u$；
2. 找到一个点 $v$ 满足 $tim_v\ge d$，并且 $v$ 可以覆盖 $u$，再此基础上，我们要求 $v$ 的深度最小；
3. 令 $v$ 为最初感染的节点，覆盖所有 $v$ 可以覆盖的点，并令 $ans\gets ans+1$。

考虑这个贪心为什么是正确的。

如图，点 $p$ 为 $\operatorname{lca}(u,v)$。

因为点 $v$ 的深度最小，所以选择点 $v$ 可以覆盖尽可能多的 $p$ 以上的点。

又因为点 $u$ 是未被覆盖的点中深度最大的，则 $p$ 子树内其他未被覆盖点都能被覆盖。

所以我们的贪心策略是正确的。

这样我们就得到了一个 $O(n^2)$ 的做法，考虑进行优化。

---

不难发现，在如上过程中，寻找点 $v$ 是困难的，但是寻找点 $p$ 是简单的，因为点 $p$ 是点 $u$ 的祖先。

对于每一个点 $i$，我们求出 $ b_i=\max\limits_{tim_j\ge d}(dep_i+d-\operatorname{dis}(i,j)) $ 与 $ c_i=\min\limits_{tim_j\ge d}(dep_i-d+\operatorname{dis}(i,j)) $。

首先容易发现 $b_i,c_i$ 取得最值的 $j$ 是相同的。

分析可以发现，若存在两个点 $x,y$ 满足 $x$ 是 $y$ 的祖先，则有 $b_x\le b_y$ 与 $c_x\le c_y$。

那么点 $p$ 只需要满足 $b_p\ge dep_u$ 即可，又因为 $b_p$ 的单调性，我们容易使用二分找出合法的 $p$。

我们需要点 $v$ 深度最小，由于 $c_p$ 的单调性，这个条件也可以转为 $c_p$ 最小，进而转化为 $p$ 深度最小。

通过上面的分析，我们已经可以找出最优的 $p$，那么我们就可以直接知道对应的 $v$ 了。

---

我们离正解就剩下了最后一步，维护这棵树上的点。

我们的操作分为两种：

• 选定一个点 $v$，覆盖所有满足 $\operatorname{dis}(u,v)\le d$ 的点 $u$；
• 对于一个点 $u$，查询点 $u$ 是否已经被覆盖。

考虑询问操作。

显然，对于一个点 $u$，若有点 $v$ 覆盖点 $u$，那么就有两种情况，$v$ 在 $u$ 子树内和 $v$ 不在子树内。

若 $v$ 在 $u$ 子树内，则 $dep_u+d\ge dep_v$，使用树剖容易维护这种情况。

若 $v$ 不在子树内，设 $p=\operatorname{lca}(u,v)$，则有 $dep_u+dep_v-2dep_p\ge d$。

那么对于每一个点 $i$，使用树剖维护 $l_i=\max\limits_{j\text{在子树内且已经被操作}}dep_j-2dep_i$。

对于查询操作，我们需要对于所有 $u$ 的祖先 $p$ 查询是否有 $dep_u+l_p\ge d$。

本质为链最值操作，容易使用树剖维护。

对于修改操作，我们需要对于所有 $v$ 的祖先 $p$ 更新 $l_p\gets \max(l_p,dep_v-2dep_p)$。

相当于是一条链对一个等差数列取 $\operatorname{max}$，注意到等差数列公差为定值 $2$，所以也容易使用树剖维护。

综上所述，我们可以使用树剖维护这两种操作。

---

最终的过程，就是我们每一次找当前最深的点，查询它有没有被覆盖。

如果没有被覆盖，就找到上述的 $v$ 并进行覆盖操作，直至所有点被覆盖。

时间复杂度 $O(nq\log^2n)$。由于树剖常数小，可以通过。

更好的解决方案：

1. 对于树上的每一条重链，我们单独开一棵动态开点线段树，可以令树剖常数变小；

2. 由于瓶颈主要在于 $v$ 不在 $u$ 子树内的情况，而这一部分只有链操作，所以可以使用全局平衡二叉树换掉树剖，时间复杂度 $O(nq\log n)$。

   可能是因为我写的屎，所以这种方案应该是没有第 $1$ 种跑的快。

代码

由于题解是后来写的，补充了很多细节，所以这份代码和上面讲的有一些细节不同。

代码有点长，挂这里。

感谢观看！