POI的经典trick：二分+DP，30min左右切了。
Description
给一颗 \(n\) 个节点的树（\(n \le 3 \times 10^5\)），初始时 \(1\) 号节点被染黑，其余是白的。
两个人轮流操作，一开始 B 在 \(1\) 号节点。
每一轮，A 选择 \(k\) 个点染黑，然后 B 走到一个相邻节点，
如果 B 当前处于白点则 B 胜，否则当 A 将所有点染为黑点时 A 胜。
求能让 A 获胜的最小的 \(k\).
Solution
一看，一棵树，再一看，求最小，第一反应是树上DP。
设 \(f_i\) 表示考虑以 \(i\) 为根的子树的最小的 \(k\)。
不行，是个 OIer 都不会这么设计。（明显状态无法从子树一个个推到根节点）
仔细地看看题，手元一下样例。
发现假设 B 从 \(u\) 走到了一个儿子 \(v\)，那么决策就只和以 \(v\) 为根的子树有关系，其他的分支就没必要考虑了。
再细一点，可以知道，每一步只需要关注下一层（儿子节点）就行了，子树的话一层层就推下来了。
现在把 \(k\) 再压进状态里面方便枚举。
那么设 \(f_{k,i}\) 表示当前每一次可以涂 \(k\) 个点的时候， \(i\) 的儿子还需要涂多少次来让所有儿子都变黑。
从叶子节点开始层层上推，如果 \(f_{k,1} \le 0\) 的话那么 \(k\) 就是可行的。
DP 完之后从 \(1\) 开始找到所有可能中最小的 \(k\) 即可。
这时候，你看到了 \(n=3\times 10^5\) ，真不幸，你的做法被卡了！
考虑怎么优化。
设想，假设你 \(k=3\) 就能满足条件，那 \(k=4,5,6...\) 有必要出现吗？
扩展一下就是，所有 \(f_{k,1}<0\) 的情况都可以归类到 \(f_{k,1}=0\)。（不归类会炸——）
所以你发现 \(k\) 具有单调性，而且其实正常做法不好求，那么就可以掏出二分了！
（顺便 \(f\) 的第一维 \(k\) 就不用了，空间复杂度优秀）
我们在值域 \([1,n+1]\) 上二分，每一次 check 的时候 DP 一下看 \(f_1\) 是否为 \(0\) 即可。
状态就是 : \(f_u\) 表示 \(u\) 的所有儿子在当前的 \(k=mid\) 的情况下还需要涂多少次。
方程也很简单： \(f_u=tot_{son}+\sum f_v - k,(v\in \text{Son(u)})\)，\(tot_{son}\) 是儿子个数。
Code：
#include<bits/stdc++.h>
using namespace std;
#define special if(n==1) return puts("0"),0;
// n=1 要特判！
const int si=3e5+10;
struct Tree{
int ver,head,Next;
}e[si<<1];
int cnt=0;
void add(int u,int v){
e[++cnt].ver=v,e[cnt].Next=e[u].head;
e[u].head=cnt;
}
int n,k;
int f[si];
void dp(int u,int fa){
int son=0;
for(register int i=e[u].head;i;i=e[i].Next){
int v=e[i].ver;
if(v==fa) continue;
dp(v,u),son+=f[v],son++;
}
son-=k,f[u]=son;
if(f[u]<0) f[u]=0;
return;
}
bool check(int mid){
k=mid,dp(1,0);
return f[1]==0;
}
int main(){
scanf("%d",&n);special;
for(register int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
int l=1,r=n+1,ans;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid,ans=mid;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}