P4654 [CEOI2017] Mousetrap 题解

· · 题解

见到两遍了，写一下题解。

这道题目也是我写出的第一道黑题。

以下均为考场思路。

文章同步于 CSP 2023 游记。

解题思路

记 S 到 T 的路径为主干道，与主干道直接相连且不在主干道上的边为支路。

手玩一下发现人和老鼠的操作必定按照下面四个步骤依次进行：

  1. 老鼠沿主干道移动，同时人堵住一条支路。
  2. 老鼠在某个节点沿一条支路进入一个子树，然后被自己弄脏的边堵死在某个叶子结点。
  3. 人在老鼠被堵死的时候堵住老鼠当前位置到 T 的路径上的所有支路，然后清理老鼠当前位置到 T 的路径上所有被弄脏的边。
  4. 老鼠此时只能走到 T，游戏结束。

步骤 1 和 3 的人的操作比较难模拟，注意到操作 2 是树上操作，可以用树形 DP 来计算，那么先考虑操作 2。

记 f_x 表示若老鼠进入该树根节点后，在该树内的操作数。

考虑当某个节点的所有子树都计算完毕后，老鼠进入该节点时人类的操作：

显然让老鼠进入 f 值次大的子树一定比老鼠进入 f 值最大的子树好，那么转移就应该从 f 值次大的子树进行转移。

老鼠进入该子树后，在操作 3 时还需要堵住其其他支路。可以直接在此处计算。那么转移方程显然：记 cnt_x 表示 x 子树个数，son_x 表示 x 的某个子树，则有：

f_x=\underset{y\in son_x}{\operatorname{2ndmax}}{f_y}+cnt_x

把步骤 2 考虑完之后尝试考虑步骤 3，假定老鼠在步骤 2 中从节点 p 进入子树 x 然后被困死，那么从 p 到 T 的所有支路都必须堵住。这个可以用前缀和维护，不多赘述。

步骤 1 堵路的操作比较难想，这时我们可以转换思路。注意到答案具有单调性，可以二分答案转化成判定性问题。

假定老鼠走主干道已经到达了某个节点 p，它得知你期望的操作次数为不大于 m，那么考虑老鼠会如何进入子树。

如果现在已经堵住了 u 次路，对于某一个子树 x，老鼠只会在 f_x+sum_p+u \gt m 的情况下才会钻进这个子树。

正确性证明：若 f_x+sum_p+u \leq m，那么老鼠进入这个子树后，人必定能用 f_x+sum_p+u 次操作完成游戏，由此说明人可以在 m 次操作内完成游戏。在目标明确的情况下，老鼠的目的就是证明人不可以在 m 次操作内完成游戏。因此，进入该子树一定对老鼠不优。

既然对于每个子树钻或不钻对于老鼠而言是一定的，那么人的操作就显然了：人需要按照从 S 到 T 的顺序堵住所有老鼠可能会进入的子树与主干道的相连边。如果老鼠在到达某个节点的时候还有可钻的子树，那么说明答案大于 m，否则 m 就是一个可行的答案。

至此，这道题的思路就明确了。

代码

可以结合代码食用，虽然代码没写注释，但是思路大致清晰。

代码太长，扔到剪贴板了。