RT，很作死地使用入度算出儿子数量

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll int 
#define v1 q[i].to
using namespace std;
const ll N=4e6;
ll n,m,in[N],cnt,head[N],f[N],mid,l,r,ans;

struct tree_map{
	ll to,nxt;
}q[N];

void add(ll u,ll v){
	q[++cnt].to=v;
	q[cnt].nxt=head[u];
	head[u]=cnt;
	in[u]++;
}

void dfs(ll u,ll fa){
	ll sum=in[u]-1;
	for(ll i=head[u];~i;i=q[i].nxt){
		if(v1!=fa){
			dfs(v1,u);
			sum+=f[v1];
		}
	}
	f[u]=max(0,sum-mid);
}

int main(){
	memset(head,-1,sizeof head);
	scanf("%d",&n);
	for(ll i=1;i<n;i++){
		ll a1,a2;
		scanf("%d%d",&a1,&a2);
		add(a1,a2);
		add(a2,a1);
	}
	l=1,r=n-1;
	while(l<=r){
		mid=(l+r)/2;
		dfs(1,0);
		if(f[1]==0){
			ans=mid,r=mid-1;
		}
		else l=mid+1;
	}
	printf("%d",ans);
}