§ 题意简述

见题意翻译。

§ 题解

没有什么好的方法求 $k$ 的值，我们考虑二分。

这个二分的单调性是显然的，考虑怎么判断。

可以通过树形DP的方式来判断。

设 $F_{i}$ 为以 $i$ 为根节点的子树最少还需多染几个节点可以使得A获胜。

那么容易得出转移方程：

其中 $k$ 为当前的二分值。

可知只要 $F_{1}=0$ 就是一个可行方案。

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 3e5 + 5;
int n, dp[Maxn];
vector < int > G[Maxn];

void dfs(int x, int fa, int k)
{
	dp[x] = 0;
	for (unsigned i = 0; i < G[x].size(); ++i)
	{
		int y = G[x][i];
		if (y == fa)	continue;
		dfs(y, x, k);
		dp[x] += dp[y] + 1;
	}
	dp[x] = max(dp[x] - k, 0);
}

bool Check_Feasic(int x)
{
	dfs(1, 0, x);
	if (dp[1] == 0) 	return 1;
	else 	return 0;
}

int Binary_Search(int l, int r)
{
	int ans = l;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (Check_Feasic(mid))	ans = mid, r = mid - 1;
		else	l = mid + 1;
	}
	return ans;
}

signed main()
{
	scanf("%d", &n);
	for (int i = 1; i < n; ++i)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	printf("%d\n", Binary_Search(0, n));
	return 0;
}