给你一棵以1为根的有根树，初始除了1号点为黑色外其余点均为白色。Bob初始在1号点。每次Alice将其中至多k个点染黑，然后Bob移动到任意一个相邻节点，重复这个过程。求最小的k，使得无论Bob怎样移动，经过的节点都是黑色节点。

输入

第一行，包含1个整数，n，表示建筑的数量。

接下来n-1行，每行两个整数u、v（1≤u,v≤n，u≠v），表示建筑u和建筑v之间有一条魔法道路。

数据保证任意两个建筑连通。

1≤n≤300000。

输出

输出一个整数k，表示最少需要派出施用咒语的成员数。

样例输入

7

1 2

1 3

2 5

2 6

7 2

4 1

样例输出

3

---

题解

二分+树形dp

建议大家读读原题面 = =

读懂题后可以发现：

Bob（伏地魔）的移动路线一定是从根节点到一个叶子节点的一条路径，因为走回头路实在是太傻逼了... 

Alice（凤凰社）只需要每次将每次移动的叶子节点染黑即可，每次一定是优先染叶子节点（因为下一步就要走到），多余的补后面的部分。

答案显然具有单调性，考虑二分答案。

对于二分的 $k=mid$ ，使用树形dp判定：

设 $f[x]$ 表示Bob走到了 $x$ 节点，仅有 $x$ 染黑，需要额外染多少个黑点才能够完成（也就是说之前需要多出多少个剩余操作次数才能够满足条件）。

那么对于 $x$ ，显然 $f[x]=\text{max}(\sum\limits_{fa[y]=x}f[y]+son[x]-mid,0)$ （$son[x]$ 表示 $x$ 的儿子个数），因为子节点需要染黑，每个儿子都需要补全（否则Bob可以选择该儿子）。而这一个点多余的的不能补给路径上之前的点，因此和 $0$ 取 $\text{max}$ 。

如果 $f[1]=0$ ，说明不需要额外补充节点，$mid$ 可行；否则 $mid$ 不可行。

时间复杂度 $O(n\log n)$ 。

#include 
     
      #include 
      
       #define N 300010using namespace std;int head[N] , to[N << 1] , next[N << 1] , cnt , son[N] , f[N] , mid;inline void add(int x , int y){	to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void init(int x , int fa){	int i;	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa)			son[x] ++ , init(to[i] , x);}void dfs(int x , int fa){	int i;	f[x] = son[x] - mid;	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa)			dfs(to[i] , x) , f[x] += f[to[i]];	if(f[x] < 0) f[x] = 0;}int main(){	int n , i , x , y , l , r , ans;	scanf("%d" , &n);	for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);	init(1 , 0);	l = 0 , r = n;	while(l <= r)	{		mid = (l + r) >> 1 , dfs(1 , 0);		if(f[1] == 0) ans = mid , r = mid - 1;		else l = mid + 1;	}	printf("%d\n" , ans);	return 0;}