rt

30pts求调

#include<bits/stdc++.h>
const int N=3e5+5; 
using namespace std;
//题意转换：每次填k个点，从下往上，任意时刻所有节点的所有子节点被都填或都没被填 
int f[N];

int cnt=0,head[N*2];
struct Node{
	int v;int next; 
}e[N*2];
inline void addedge(int u,int v){
	e[++cnt].v=v;e[cnt].next=head[u];head[u]=cnt;
}

void dp(int now,int father,int k)
{
	int ie=0;
	for(int i=head[now];i;i=e[i].next)
		if(e[i].v!=father)
		{
			int next=e[i].v;
			dp(next,now,k);
			f[i]+=f[next];//点子树的无法填满的点数向上传递 
			ie++;
		}
	f[now]=max(0,f[now]+ie-k);//当前点所有子树的无法填满的点数 
}

int n;
int main()
{
	cin>>n;
	if(n==1){cout<<"0"<<endl;return 0;}
	for(int i=1,u,v;i<=n-1;++i)
	{
		cin>>u>>v; 
		addedge(u,v);addedge(v,u);				 
	}

	int l=1,r=n-1,ans=0;
	while (l<r)//二分答案 
	{
		int mid=(l+r)>>1;
		memset(f,0,sizeof(f));
		dp(1,0,mid);
		if (f[1]==0)//树满足条件 
			r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}