CF1946C Tree Cutting

二分 深度优先搜索

题目大意

给定一个 $n$ 个结点的数，现在要你断掉 $k$ 条边，使得所有联通块当中的最小大小最大。

思路

最小值最大，而且答案满足单调性，那么我们就可以使用二分求解，然后贪心地对可能的答案进行判断。不难想出，越在下面满足条件的地方进行切分，那么分出的联通块数量也是最大的，最后就看一看是否满足切分了 $k$ 刀即可。

注意一个特判，如果最后一块不够的话就少切一刀。

代码

#include <iostream>
#include <vector>
 
using namespace std;
 
const int kMaxN = 1e5 + 5;
 
int t, n, m, k, cnt, ans;
vector<int> e[kMaxN];
 
int dfs(int x, int f) {
  int sum = 1;           // 可用的结点数量
  for (int i : e[x]) {   // 枚举所有儿子
    if (i != f) {
      sum += dfs(i, x);  // 递归并加上儿子可用的结点
    }
  }
  if (sum >= m) {  // 如果可用结点数量够了
    cnt += !f;     // 在不是根结点的情况下断边
    return 0;      // 子树被单独分出来了
  }
  return sum;      // 否则返回可用的结点
}
 
bool check() {
  cnt = 0;                  // 清零
  int res = dfs(1, 0);      // 根结点的可用数量
  res && res < m && cnt--;  // 不够的话少切一条边
  return cnt >= k;          // 判断是否能够切 k 刀
}
 
int main() {
  for (cin >> t; t; t--) {
    cin >> n >> k;
    fill(e + 1, e + n + 1, vector<int>());
    for (int i = 1, u, v; i < n; i++) {
      cin >> u >> v;
      e[u].push_back(v);
      e[v].push_back(u);
    }
    for (int l = 1, r = n; l <= r; ) {
      m = (l + r) >> 1;
      if (check()) {
        ans = m, l = m + 1;
      } else {
        r = m - 1;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}