一. 砍树

（1）思路：

· 答案具有单调性：对于正确答案 ans ，小于 ans 的都一定符合条件，大于 ans 的一定不符合条件，因此可以二分答案。

· 先dfs到叶节点，再逐步递归出来，过程中节点数增加，一旦达到 mid ，ans 加一，同时向上贡献节点数变为零。

（2）代码：

#include #define LL long long using namespace std;  const int N = 1e5 + 5;  int n, k, ans; vector G[N];   int dfs(int u, int fa, int mid) { 	int s = 1; 	for (auto v : G[u]) 	{ 		if (v == fa) 			continue; 		s += dfs(v, u, mid); 	} 	if (s >= mid) 	{ 		ans ++; 		return 0;					// µ±Ç°½Úµã¿ªÊ¼µÄ×ÓÊ÷²»»áÔÙ¶ÔÉÏÃæ×ö³ö¹±Ï×  	} 	return s;						// µ±Ç°½ÚµãÄܹ»ÏòÉÏ×ö³ö¹±Ï×  }  bool check(int mid) { 	ans = 0;						// ans ²»Êdzõʼ»¯Îª 1  ²¢²»Äܹ»±£Ö¤ËùÓнڵãÊý±¾Éí¾Í´óÓÚ mid  	dfs(1, -1, mid); 	return ans >= k + 1; }  int main() { 	cin >> n >> k; 	for (int i = 1; i < n; i ++) 	{ 		int u, v; 		cin >> u >> v; 		G[u].push_back(v), G[v].push_back(u); 	} 	int l = 1, r = n + 1, mid; 	while (l + 1 < r) 	{ 		mid = l + (r - l) / 2; 		if (check(mid)) 			l = mid; 		else 			r = mid; 	} 	cout << l; 	return 0; }