题意

给定两个人的树上博弈规则。小 N 初始时在节点 $S$ ，小 Y 需要通过一些操作“强迫”小 N 最后到达节点 $T$ 。小 N 想要让小 Y 的操作尽量多，而小 Y 希望自己的操作尽量少。求解两人都采取最优决策时，小 Y 的操作次数。 每一轮中操作如下：

• 小 Y 可选的操作有：恢复一条小 N 删除的边 ；或者删除一条边；或者跳过这次操作（不计入答案）。

• 小 N 接下来执行：如果没有相邻的点，则停留在原地；否则选择一条出边走过去，并将走过的边删除。

$n\leq10^6$ 。

题解

遇到这种问题不要慌，分析它的决策。

考虑往儿子走的决策。设 $f_u$ 表示在以 $u$ 为根的子树中，初始时小 N 从 $u$ 出发，最后被迫回到 $u$ 的最小代价。在 $u$ 的子树中，小 N 一定会选择走 $f$ 最大的一个儿子，那么小 Y 就会选择堵住这个儿子，小 N 只能选择儿子中的次大值，于是有：

$$f_u=|\text{son}(u)|+\text{second}\max_{v\in\text{son}(u)}f_v $$

分析小 N 决策，发现他可以选择往上走若干个然后再走到子树。那么二分小 Y 操作次数 $\text{mid}$ ，把最优化决策转化为判断决策问题。设 $g_u$ 表示根节点到 $u$ 的路径中所有分叉路数量。然后往上走的过程中，要断 $f_v+g_u>\text{mid}$ 的边。

代码

const int N = 1e6 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, T, S;
	vector <int> e[N];
	int f[N], g[N], fa[N];
	void dfs (int u, int fat) {
		fa[u] = fat;
		int son = e[u].size() - (!!fa[u]);
		if (fa[u]) g[u] += son - 1;
		int mx = 0, se = 0;
		for (int v: e[u]) {
			if (v == fa[u]) continue;
			g[v] = g[u];
			dfs(v, u);
			if (f[v] > mx) se = mx, mx = f[v];
			else if (f[v] > se) se = f[v];
		}
		f[u] = se + son;
   	}
	bool check(int mid) {
		int u = S, cnt = 0, dis = 0, lst = -1;
		for (; u != T; lst = u, dis++, u = fa[u]) {
			int tmp = cnt;
			for (int v: e[u]) {
				if (v != lst && v != fa[u] && f[v] + g[u] + tmp + 1 - (u != S) > mid) cnt++;
			}
			if (cnt > dis + 1 || cnt > mid) return 0;
		}
		return 1;
	}
	int main () {
		n = Read(), T = Read(), S = Read();
		for (int i = 1; i < n; i++) {
			int u = Read(), v = Read();
			e[u].emplace_back(v);
			e[v].emplace_back(u);
		}
		dfs (T, 0);
		int l = 0, r = n, ans;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (check(mid)) r = (ans = mid) - 1;
			else l = mid + 1;
		}
		printf ("%d\n", ans);
		return 0;
	}
}

int main () {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	Main::main();
	return 0;
}