题解：P15268 「UTOI 1C」Delirium Of Aeons

zjinze · 2026-02-11 19:02:25 · 题解

简单贪心，因为神秘错误虚空调式半年。

链的部分分启示我们，令树的直径的端点为根，每次拿出一条链，然后把这链上每一个点划到一个连通块中，这样每次答案只会加一，因为和叶子相邻的连通块只有一个（除第一次拿出链时答案会加二，因为根的度数为一），然后每次连通块的个数加上链的长度，剩余没有被划分的点可以随意合并到相邻的连通块，对答案不造成影响，然后做完了。

#include<bits/stdc++.h>
using namespace std;
const int kN = 2e5 + 10;
int n, m, son[kN], is[kN], rt;
vector<int> vec[kN];
int len[kN], in[kN];
void dfs(int now,int f){
  for(int to : vec[now]){
    if(to == f) continue;
    dfs(to, now);
    if(len[to] > len[son[now]]) son[now] = to;
  } len[now] = len[son[now]] + 1; is[son[now]] = 1;
}
namespace SPB{
  int dep[kN], son[kN], mx;
  void dfs(int x, int fa){
    son[x] = x;
    for(int j : vec[x]){
      if(j == fa) continue;
      dfs(j, x);
      if(mx < dep[x] + dep[j] + 1) mx = dep[x] + dep[j] + 1, rt = son[j];
      if(dep[j] + 1 > dep[x]){
        dep[x] = dep[j] + 1; son[x] = son[j];
      }
    }
  }
  void main(){
    for(int i = 1; i <= n; i++) dep[i] = 0, son[i] = 0; 
    mx = 0;
    dfs(1, 0);
    return ;
  }
}
int b[kN];
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  int T; cin >> T;
  while(T--){
    cin >> n >> m;
    for(int i = 1; i < n; i++){
      int u, v; cin >> u >> v;
      vec[u].push_back(v);
      vec[v].push_back(u);
    } 
    rt = 0;
    SPB::main();
    dfs(rt, 0); 
    if(m == 2){
      cout << 2 << '\n';
    }
    else{
      int ans = 0, tot = 0;
      for(int i = 1; i <= n; i++) if(!is[i]) b[++tot] = len[i];
      sort(b + 1, b + tot + 1);
      for(int j = tot; j >= 1; j--){
        ans++; m -= b[j];
        if(m <= 0) break;
      } cout << ans + 1 << '\n';
    } 

    for(int i = 1; i <= n; i++) vec[i].clear();
    for(int i = 1; i <= n; i++) len[i] = son[i] = is[i] = in[i] = 0;
  }
  return 0;
}