【题解】P4654 [CEOI2017] Mousetrap

· · 题解

前言

模拟赛之后被胁迫上去讲这题，没怎么准备，然后就在几个省的 OIer 面前当小丑。。倒是把我自己讲得很明白，但感觉对其他人不是很负责任，就来赎罪一下。。

更好的阅读体验。

题意

题目链接。

分析

  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

#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;
}