40pts神秘思路求hack

#include <bits/stdc++.h>

using namespace std;

const int N = 300005;
int n,dep[N],cnt[N],mx;
vector<int> e[N];

void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	mx=max(mx,dep[x]),cnt[dep[x]]++;
	for(int i=0;i<e[x].size();i++){
		int y=e[x][i];
		if(y==fa) continue;
		dfs(y,x);
	}
}
bool check(int x){
	int res=x;
	for(int i=2;i<=mx;i++){
		if(res<cnt[i]) return false;
		res=res-cnt[i]+x;
	} return true;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v; cin>>u>>v;
		e[u].push_back(v),e[v].push_back(u);
	}
	dfs(1,1);
	int l=0,r=N;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l;
	return 0;
}