P1084 [NOIP2012 提高组] 疫情控制
思路：注意到答案有单调性，考虑二分答案。
现在由最优性问题转换为判定性问题。
我们很容易注意到一个性质：
[*]一个军队不停的往上跳是更优的。
[*]因为可以覆盖住更多的叶子节点。
那么对于二分答案的 \(mid\)，我们只需要求出每一个军队在 \(mid\) 时间内能跳到的最高的那个点，然后判定一下是否覆盖了所有叶子节点即可。
但是这样会存在一个问题，即若当前这个点为 \(1\) 的儿子，且有多个军队跳到，则可能可以支援一下 \(1\) 号点的其它儿子（因为检查点不能放在 \(1\) 上，则可能还有空余的时间经过 \(1\) 走到 \(1\) 的其它儿子）。
先来考虑一个简单的问题：
[*]若已知每个检查点的位置，如何判断是否覆盖了所有叶子节点；设 \(g_i\) 表示 \(i\) 处是否有检查点。
考虑先对于每个叶子节点标一个号（按照 dfn 序的大小），那么我们可以搜的时候预处理出 \(l_i,r_i\) 表示 \(i\) 这棵子树的叶子节点的编号为 \(\)。
则对于一个检查点 \(x\)，它可以覆盖 \(\) 这个范围，令这个区间都加 \(1\)，最后检验一下是否每个叶子节点都被加了至少一次，可以用差分实现。
但是这样就无法考虑支援问题，因为我们需要知道 \(1\) 号节点的每一个儿子所在子树的叶子节点是否全部都被覆盖。
考虑树形 dp，令 \(dp_u\) 表示点 \(u\) 所在子树的叶子节点是否都被覆盖了，则状态转移方程为：
\
若 \(1\) 号点的儿子 \(u\) 满足 \(dp_u=0\)，那么该点需要支援，将所有需要支援的点按照到 \(1\) 的距离排序。
则对于可以发动支援的点 \(v\)，设 \(v\) 到达 \(1\) 后还可以走 \(k\) 的距离（需要按 \(k\) 从小到大排序），那么我们可以贪心在需要支援的点集中找到距离 \(\le k\) 且距离最大的点，可以用 set 维护插入，删除，二分操作。
要注意一下细节，即若 \(v\) 不在 \(v\) 上设置检查点，也可以使得 \(dp_v=1\)，那么我们可以将 \(v\) 上的军队全部派出去支援；否则需要留一个军队守家，我们可以留剩下能走距离最小的那个军队守。
此时还会有一个问题别问我为什么贪心有这么多细节，即若这个点上的某一军队到不了任何一个需要支援的点且不需要守家，但是可以到一个需要留一个军队守家的点，且那个守家的军队可以走足够的距离去支援一个点，那么可以让这个点上的军队去代替它守家，这样会更优，称之为二次支援。
考虑在一次支援完后记录一下所有在守家且可以支援的点和所有无法支援却不需要守家的点。
那么二次支援和一次支援差不多，对于无法支援却不需要守家的点的点 \(u\)，设还可以走 \(k\) 的距离，那么我们可以在所有在守家且可以支援的点中找到距离 \(\le k\) 且距离最大的点，也可以用 set 维护。
然后再来考虑跳跃的问题：
[*]如何求出一个点在 \(mid\) 时间内能上跳到的最高的点。
很容易想到二分跳的次数然后长链剖分求 \(k\) 级祖先，这样是 \(\log^2 N\) 的，考虑优化。
考虑倍增与贪心，令 \(F_{i,j}\) 表示 \(i\) 的 \(2^j\) 级祖先，\(W_{i,j}\) 表示 \(i\) 到它的 \(2^j\) 级祖先的距离，状态转移方程为：
\
\
那么可以直接贪心从高位到低位枚举二级制位 \(i\)，若 \(W_{x,i} \le mid\)，则令 \(mid \gets mid - W_{x,i}\)，然后令 \(x\) 跳到 \(F_{x,i}\) 处；最后跳到不能再跳即可。
设 \(N,M\) 同阶，则总时间复杂度为 \(O(N \log N \log W)\)。
完整代码：
#include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=5e4+10,M=16;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c
页:
[1]