P9983 [USACO23DEC] Cowntact Tracing P
Wuyanru
·
·
题解
开场不到 2h 过了这题，虽然复杂度比正解大点，但是没有关系。
好像是这次铂金组的最难题？但是我不会这次的 T3 啊。
题目链接。
题意
现在有一棵 n 个点的树，每一个节点上都有一头牛。
这群牛感染了一种病毒，每一天，若一头未被感染的牛与一头已被感染的牛相邻，这头牛下一天就会被感染。
现在告诉你 d 天以后哪些牛被感染了，求第 0 天时最少有几头牛被感染，或报告无解。
$ 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 $ 种跑的快。
## 代码
由于题解是后来写的，补充了很多细节，所以这份代码和上面讲的有一些细节不同。
代码有点长，挂[这里](https://www.luogu.com.cn/paste/2fpdrg7p)。
感谢观看！