前言

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

题意

分析

以 \(t\) 为根，我们的目的是让老鼠走到根的操作数最小。
观察老鼠的动向，显然老鼠只要一往下走，那么除非管理员将它上方的道路擦干净，否则它就只能继续往下走。当然，老鼠可能也会往上走（待会儿再考虑）。
若老鼠已经往下走，但未走到叶子节点，那么我们不用立刻将其往上的一条路的分支堵住，因为当老鼠自己到叶子节点之后就动不了了，这时我们再把从这个叶子节点往上直到根的路径上所有的分支（不包括根的分支）全部堵上，最后再一一擦干净老鼠的边，使其被迫走向根节点。如果不堵分支，那么老鼠走入分支消耗的操作数一定大于等于 \(1\) 即直接堵的操作数。
因为是最优策略，所以每个点的最优操作数之类的信息唯一。
根据 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}\) 的贡献，显然）。
考虑如何求 \(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\)。
考虑由 \(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\) 的，老鼠已经自己弄脏了一条边，管理员就可以少堵一条。
然后我们会发现我们记录的值似乎没什么卵用。
但是先别重开。再次分析老鼠的固定策略。显然老鼠可以向上走，进入一条比直接从 \(u\) 往下走更优的分支，最大化答案。
考虑简化问题。考虑二分。对于一个待检查的最大操作数 \(T\)，显然此时问题变为了：老鼠能不能使最大操作数大于 \(T\)。
考虑简化老鼠的策略，并分析整个游戏的固定流程分层。老鼠显然可以先往上走 \(k\) 次（\(k \geq 0\)）。然后选择当前点的一个分支，从当前点走入这个分支，（根据 4 知）老鼠走到叶子节点，管理员堵分支，老鼠出来走入根节点 \(t\)，游戏结束。
考虑 11 中“从当前点走入这个分支”的隐含内容，显然走入分支后，剩下的操作数由 \(cnt\) 可以直接计算。
考虑二分检验时模拟过程。记 \(\mathrm{check}(u, p, q)\) 表示当前在 \(u\) 点，最多还可以进行 \(p\) 次操作，管理员提前保留了 \(q\) 次操作，能否满足。这里需要说一下，因为两方都执行最优，所以管理员、老鼠互相可以知道对方的一定的策略。所以管理员会在每次可操作时堵上老鼠走入会使总操作次数大于 \(p\) 的分支。因为管理员执行最优，且方案一定，所以管理员可以在不需要堵当前点的分支的时候提前堵后面的点，形象地说，管理员将操作数保留累积下来，在以后的点中使用。
考虑如何实现 \(\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\)。
所以每次检查答案 \(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;
}