前言
模拟赛之后被胁迫上去讲这题，没怎么准备，然后就在几个省的 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;
}