Description：

给一棵树，其中一个点是陷阱，另一个点有老鼠，老鼠每经过一条边这条边就不能再走，管理员可以封住一条边或者把老鼠经过的边让他还能走，管理员希望最小化将老鼠赶到陷阱，老鼠希望最大化，问双方都最优时的操作数。

$1\leqslant n\leqslant 10^6$

Solution：

假设陷阱是根。

首先管理员如果不管的话，那么老鼠要么一路走到陷阱，要么往下走到某棵子树，因为退路被封死了所以最后一定会到某个叶节点，这个时候管理员只要把所有支路都封死，然后把从这个点到根的路径打开老鼠就只能到根。

所以老鼠的策略一定是先往上走一截，然后一路走到叶子停下来，设 $f[i]$ 表示老鼠进入了子树 $i$ ，再把老鼠赶回 $i$ 所需要的步数，那么转移为： $$ f[k]=\mathrm{secmax}_{i\in son[k]}{f[i]}+deg[k]-1 $$ 然后会发现我们并不知道老鼠进入哪棵子树可以拖延最久的时间，那么我们就可以二分，我们对于每个分支，如果老鼠进去会超时的话，我们都必须在老鼠到达那个位置之前或者当时把他封住。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,t,m;

#define MAXN 1000010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int fa[MAXN];

int f[MAXN];

int deg[MAXN];

void prework(int k)

{

	deg[k] = 0;

	int maxv = 0,secv = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		fa[e[i].to] = k;

		++deg[k];

		prework(e[i].to);

		if(f[e[i].to] >= maxv)

		{

			secv = maxv;

			maxv = f[e[i].to];

		}

		else if(f[e[i].to] > secv)secv = f[e[i].to];

	}

	f[k] = secv + deg[k];

	return;

}

int s[MAXN],top = 0;

int sumd[MAXN];

bool check(int v)

{

	int sum = 0;

	for(int x = 1;x <= top;++x)

	{

		int k = s[x];

		int tmp = 0;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to == fa[k] || e[i].to == s[x - 1])continue;

			if(sumd[x] + f[e[i].to] + 1 - (x != 1) > v)++tmp;

		}

		sum += tmp;v -= tmp;

		if(sum > x || v < 0)return 0;

	}

	return 1;

}

int main()

{

	scanf("%d%d%d",&n,&t,&m);

	for(int i = 1;i < n;++i)add(rd(),rd());

	prework(t);

	f[t] = 0;

	for(int k = m;k != 0;k = fa[k])s[++top] = k;

	for(int i = top - 1;i >= 1;--i)sumd[i] = sumd[i + 1] + deg[s[i]] - 1;

	int l = 0,r = 0x3f3f3f3f,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(check(mid))r = mid;

		else l = mid + 1;

	}

	cout << l << endl;

	return 0;

}