【题解】P4654 [CEOI2017] Mousetrap

# 前言 模拟赛之后被胁迫上去讲这题，没怎么准备，然后就在几个省的 OIer 面前当小丑。。倒是把我自己讲得很明白，但感觉对其他人不是很负责任，就来赎罪一下。。 [更好的阅读体验](https://www.luogu.com.cn/blog/Rong7/post-ti-xie-p4654-ceoi2017-mousetrap)。 # 题意 [题目链接](https://www.luogu.com.cn/problem/P4654)。 # 分析 1. 以 $t$ 为根，我们的目的是让老鼠走到根的操作数最小。 2. 观察老鼠的动向，显然老鼠只要一往下走，那么除非管理员将它上方的道路擦干净，否则它就只能继续往下走。当然，老鼠可能也会往上走（待会儿再考虑）。 3. 若老鼠已经往下走，但未走到叶子节点，那么我们不用立刻将其往上的一条路的分支堵住，因为当老鼠自己到叶子节点之后就动不了了，这时我们再把从这个叶子节点往上直到根的路径上所有的分支（不包括根的分支）全部堵上，最后再一一擦干净老鼠的边，使其被迫走向根节点。如果不堵分支，那么老鼠走入分支消耗的操作数一定大于等于 $1$ 即直接堵的操作数。 4. 因为是最优策略，所以每个点的最优操作数之类的信息唯一。 5. 根据 4 提供的思路，考虑 $f_u$ 表示老鼠从 $u$ 点出发往下折腾一通再被迫回到 $u$ 点**在 $u$ 子树内**消耗的操作数。考虑 DP，由于每次老鼠出发前管理员可以先进行一次操作。只观察 $u$ 点的儿子节点，发现如果不把向最大值 $(f_v)_{\max}$ 的路径堵住的话，老鼠一定选这条路往下走，折腾 $(f_v)_{\max}$ 次操作后，回到 $u$ 点；否则老鼠会向次大值 $(f_v)_{\max_2}$ 走，折腾 $(f_v)_{\max_2}$ 次操作后回到 $u$ 点。我们发现两种情况老鼠回到 $u$ 点后情况其他都一样（分支全部被堵住，只能往上走），所以选择堵 $(f_v)_{\max}$ 一定最优（我们还可能堵与它不相连的边，但贡献一定小于等于堵 $(f_v)_{\max}$ 的贡献，显然）。 6. 考虑如何求 $f_u$，发现实际上根据 3 可知管理员的固定策略，$f_u$ 分为三部分：一、选择最大的 $f_v$ 堵住，使从 $u$ 点只能走向次大 $f_v$；二、在老鼠抵达叶子后，利用多出的时间堵上 $u$ 的其他分支；三、把老鼠往下走过的路径擦干净，让老鼠走回 $u$ 点。于是有转移方程： $$ f_u=(f_v)_{\max_2}+deg_u-1 $$ 其中 $deg_u-1$ 表示 $u$ 点的分支（度数）去掉连向 $father$ 节点的，去掉 $u \to v$ 走向次大子节点的（这个不堵），加上擦老鼠 $v \to u$ 走上来的边。再加上原本的次大子节点，就是 $f_u$。 7. 考虑由 $f_u$ 求出具体的操作次数。记录 $g_u$ 表示 $u$ 到 $t$ 路径上管理员需要堵的分支（不包括 $u$ 本身的分支），则可知 $g$ 的转移方程： $$ g_u=g_{father}+\max(deg_{father} - 2, 0) $$ 解释一下，$u$ 向上的需要堵的分支，等于其 $father$ 节点向上需要堵的分支加上 $father$ 节点自己的分支（度数，去掉连向 $father$ 的父节点的边，去掉连向 $u$ 的边）（特殊情况用 $\max$ 判断）（特别地，钦定 $deg_t=1$（实际上，从本题的数据上看，不影响））。 然后我们记录一个 $cnt_u$ 表示 **从 $u$ 的父节点走入 $u$ 后** 并最终结束游戏所需要的操作数。显然 $cnt_u$ 存在唯一值。 知 $cnt_u$ 的转移方程为： $$ cnt_u=f_u+g_u+1-(father\neq m) $$ 再解释一下，$f_u$ 是老鼠往下走最终回到 $u$ 点时 $u$ 子树内的操作数贡献，$g_u$ 是管理员不得不堵的 $u$ 到 $t$ 路径上的分支，额外加的 $1$ 是擦干净 $father \to u$ 这条边的操作。最后的 $01$ 判断意思是：若父节点不是 $t$，则老鼠自己是从 $father$ 的另一个分支走入 $father$ 再走下 $u$ 的，老鼠已经自己弄脏了一条边，管理员就可以少堵一条。 8. 然后我们会发现我们记录的值似乎没什么卵用。 9. 但是先别重开。再次分析老鼠的固定策略。显然老鼠可以向上走，进入一条比直接从 $u$ 往下走更优的分支，最大化答案。 10. 考虑简化问题。考虑二分。对于一个待检查的最大操作数 $T$，显然此时问题变为了：**老鼠能不能使最大操作数大于 $T$**。 11. 考虑简化老鼠的策略，并分析整个游戏的固定流程分层。老鼠显然可以先往上走 $k$ 次（$k \geq 0$）。然后选择当前点的一个分支，从当前点走入这个分支，（根据 4 知）老鼠走到叶子节点，管理员堵分支，老鼠出来走入根节点 $t$，游戏结束。 12. 考虑 11 中“从当前点走入这个分支”的隐含内容，显然走入分支后，剩下的操作数由 $cnt$ 可以直接计算。 13. 考虑二分检验时模拟过程。记 $\mathrm{check}(u, p, q)$ 表示当前在 $u$ 点，最多还可以进行 $p$ 次操作，管理员提前保留了 $q$ 次操作，能否满足。这里需要说一下，因为两方都执行最优，所以管理员、老鼠互相可以知道对方的一定的策略。所以管理员会在每次可操作时堵上老鼠走入会使总操作次数大于 $p$ 的分支。因为管理员执行最优，且方案一定，所以管理员可以在不需要堵当前点的分支的时候提前堵后面的点，形象地说，管理员将操作数保留累积下来，在以后的点中使用。 14. 考虑如何实现 $\mathrm{check}(u, p, q)$。记 $v$ 为 $u$ 的任意儿子（当然，要求 $u$ 不是从 $v$ 走上来的）。首先为了使老鼠在当前点无法直接使操作数大于 $p$，我们要将所有 $cnt_v>p$ 的分支堵住。令这些分支的数目为 $x$，显然若 $x>p$ 或 $x>q$ 就返回 $\text{false}$。否则保留的操作数 $q$ 用去 $x$，同时老鼠往上走，时间 $+1$，所以 $q$ 又多累积了 $1$；同时最大的剩余操作数 $p$ 也用去 $x$。 这时显然有： $$ \mathrm{check}(u,p,q)=\begin{cases} \mathrm{check}(father_u,p-x,q-x+1) & p \geq x , q \geq x \\ \text{false} & \textrm{otherwise} \\ \end{cases} $$ 可以递归或循环实现。 特别地， $\mathrm{check} (t, i, j)=\text{true}$。 注意记 $u$ 是从 $last$ 走上来的，对于 $u$ 的儿子特殊判断 $v \neq last$。对于 $u=m$，$last=0$。 15. 所以每次检查答案 $T$ 是否正确的返回值就是 $\mathrm{check}(m,T,1)$。 # Code ```cpp #include <bits/stdc++.h> using namespace std; int n, t, m, a, b; int fa[1000005], dg[1000005], f[1000005], g[1000005], cnt[1000005]; int firs[1000005], nex[2000005], to[2000005], tot; void Add (int u, int v){ ++ tot; nex[tot] = firs[u]; firs[u] = tot; to[tot] = v; } void init (int u, int father){ fa[u] = father; g[u] = g[father] + max (dg[father] - 2, 0); int max1 = 0, max2 = 0; for (int e = firs[u];e;e = nex[e]){ int v = to[e]; if (v == father) continue; init (v, u); if (max1 < f[v]){ max2 = max1; max1 = f[v]; } else if (max2 < f[v]) max2 = f[v]; } f[u] = max2 + dg[u] - 1; cnt[u] = f[u] + g[u] + 1 - (fa[u] != m); } bool Check (int p){ int q = 1, las = 0; for (int u = m;u != t;u = fa[u]){ int x = 0; for (int e = firs[u];e;e = nex[e]){ int v = to[e]; if (v == fa[u] || v == las) continue; if (cnt[v] > p) ++ x; } q -= x; p -= x; if (q < 0 || p < 0) return false; ++ q; las = u; } return true; } int main (){ scanf ("%d%d%d", &n, &t, &m); for (int i = 1;i < n;++ i){ scanf ("%d%d", &a, &b); Add (a, b); Add (b, a); ++ dg[a]; ++ dg[b]; } dg[t] = 1; init (t, 0); int L = 0, R = n << 1; while (L < R){ int mid = L + R >> 1; if (Check (mid)) R = mid; else L = mid + 1; } printf ("%d\n", L); return 0; } ```