题解

思路

警察在非叶节点进入一个还有罪犯的分支后，不会在抓住该侧罪犯前原路返回，否则罪犯可用无限大速度重新逃回。因此每次真正抓到罪犯的位置可视为某个叶节点。罪犯在警察离开叶子后重新选择分布，警察再选下一个叶子，这形成一个“罪犯取最大、警察取最小”的 DP。

做法

子任务 1：枚举叶子分布

设 $F(u,k)$ 表示警察位于叶子 $u$、还剩 $k$ 名罪犯时的最优对抗时间。枚举罪犯在其他叶子上的全部整数分配 $c_v$，对每个分配，警察会选择

$$\min_{c_v>0}\bigl(\operatorname{dist}(u,v)+F(v,k-c_v)\bigr),$$

罪犯在所有分配中取最大。初始时各罪犯不能跨过警察所在的 $s$，所以对删去 $s$ 后的每个连通分支分别枚举分配。

子任务 2：有向边分割与背包

将一条有向边 $p\to u$ 看作把树分成两侧。设 $G(p\to u,a,b)$ 表示警察正进入 $u$ 侧，该侧有 $a$ 名罪犯、另一侧有 $b$ 名罪犯时的对抗值。若 $u$ 是叶子，当 $b=0$ 时结束；否则捕获当前侧后沿反向边继续。

若 $u$ 不是叶子，罪犯把 $a$ 人分到 $u$ 的子分支，警察选择最有利的分支进入。用背包依次合并各子分支，在合并中交替使用 $\max$ 和 $\min$。

子任务 3：叶子 DP 与答案二分

对每个叶子 $u$ 和剩余人数 $k$，二分 $F(u,k)$。对候选时间 $T$，对每个其他叶子 $v$ 计算最多放多少人，仍能使

$$\operatorname{dist}(u,v)+F(v,k-c_v)\ge T.$$

这些上限之和至少为 $k$ 当且仅当罪犯能把结果拖到 $T$。按 $k$ 从小到大计算，所依赖的 $F(v,k-c_v)$ 都已得到。初始状态对删去 $s$ 后的各分支使用同样的容量检查。

复杂度

第一层为叶子整数分配的指数级枚举；第二层为有向边、人数与背包合并 DP；满分层复杂度为 $O(L^2m^2\log W+n^3)$，空间 $O(nm+n^2)$，其中 $L$ 是叶子数，$W$ 是答案上界。

正确性证明

叶子状态已包含警察上一段路径造成的分隔信息；警察到达叶子后，未捕获罪犯可在警察之外的整棵树上重新分布，故状态只需记录叶子和剩余人数。对每个分布，警察选最小后续值；罪犯选使该最小值最大的分布。二分检查中的各叶子容量之和恰好判定是否存在这样的分布，因此逐层得到正确的 $F$。初始分支限制保证罪犯不能穿过警察起点，故最终答案为完整对抗的最优值。