题目大意：
给一颗树，1号节点已经被染黑，其余是白的，两个人轮流操作，一开始B在1号节点，A选择k个点染黑，然后B走一步，如果B能走到A没染的节点则B胜，否则当A染完全部的点时，A胜。求能让A获胜的最小的k
小的k能获胜大的k就一定能获胜，因此答案具有单调性，可以二分答案。
那么每次二分的答案怎么验证？
树形DP，设f[i]表示在B没走到以i为根的子树中时，需要预先在这棵子树中染色的节点数。
f[x]=max(0,∑f[to[i]]+son[x]-k)，其中to[i]代表x的子节点，son[x]代表x的子节点数。
每次DP后只要判断f[1]==0就行了。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int head[300010];
int to[600010];
int next[600010];
int ans;
int tot;
int f[300010];
int n;
int x,y;
int mid;
void add(int x,int y)
{
tot++;
next[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void dfs(int x,int fa)
{
int sum=0;
for(int i=head[x];i;i=next[i])
{
if(to[i]!=fa)
{
dfs(to[i],x);
sum+=f[to[i]]+1;
}
}
f[x]=max(0,sum-mid);
}
bool check()
{
memset(f,0,sizeof(f));
dfs(1,0);
if(f[1]==0)
{
return true;
}
return false;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
int l=0;
int r=n+1;
while(l<=r)
{
mid=(l+r)>>1;
if(check()==true)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
printf("%d",ans);
}