阅读量:0
一. 砍树
（1）思路：
· 答案具有单调性：对于正确答案 ans ，小于 ans 的都一定符合条件，大于 ans 的一定不符合条件，因此可以二分答案。
· 先dfs到叶节点，再逐步递归出来，过程中节点数增加，一旦达到 mid ，ans 加一，同时向上贡献节点数变为零。
（2）代码：
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1e5 + 5; int n, k, ans; vector<int> 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; }