80 pts 神秘二分+搜索 求hack

#include <iostream>
#include <vector>

using namespace std;

int n, ans = 0, l, r, mid;
vector <int> g[300005];

bool dfs(int u, int fa, int last) {
	bool result = true;
	int son = g[u].size() - 1 + (fa == -1);
	if (last + mid < son)
		return false;
	last +=  mid - son;
	
	for (auto v : g[u])
		if (v != fa)
			result &= dfs(v, u, last);
	
	return result;
}

int main() {
	scanf("%d", &n);
	for (int i = 1, u, v; i <= n - 1; i++) {
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	l = 0, r = n - 1;
	while(l <= r) {
		mid = (l + r) / 2;
		if (dfs(1, -1, 0)) {
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	
	printf("%d", ans);
	return 0;
}