题意:给定一棵树,将叶子节点分为尽量少个集合使集合里任一点对的距离不超过k。求最少集合数。

题解:很妙的一道题。我们可以先考虑一个点xx, 考虑它的两个儿子aa,bb。考虑贪心的思维,我们要尽可能的将叶子合在一起。题目要求最少集合数,那么我们试着将他们aa,bb两个集合合在一起。如何合在一起?

定义dis[i]表示以ii为子树的深度。那么我们只需要满足$dis[a] + dis[b] + 2 <= k $ 即可将他们合并。 那么当扩展到多个儿子的情况下。一样的道理。我们先将所有disdis排序。然后从最大的和第二大的开始判断是否可行。如果不可行,就将最大的删去(很显然这样做是对的,因为删掉小的不如删掉大的),等到发现最大和第二大的他们的$dis[a] + dis[b] + 2 <= k $成立时,此时剩余的元素必然能构造一个集合。而被删去的那些,只能单独组成集合。(且必然不能再与更大的合并了)

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;

struct edge {
    int u,v,next;
}e[N * 2];
int head[N],cnt,vis[N];
int ind[N];
int n,k,ans;
void insert(int u, int v) {
    e[++cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt;
} 
int dfs(int u) {
    vis[u] = 1;
    vector<int> t;
    for(int i = head[u]; i ; i = e[i].next) {
        int v = e[i].v;
        if(!vis[v]) {
            t.push_back(dfs(v) + 1);
        }
    }
    if(t.empty()) return 0;
    sort(t.begin(), t.end());
    while(t.size() > 1) {
        if(t[t.size() - 1] + t[t.size() - 2] <= k) break;
        else {
            ans++; t.pop_back();
        }
    }
    return t.back();
}
int main() {
    cin >> n >> k;
    for(int i = 1; i <= n - 1; i++) {
        int u,v;
        read(u); read(v);
        insert(u, v); insert(v, u);
        ind[u]++; ind[v]++;
    }
    for(int i = 1; i <= n; i++) {
        if(ind[i] > 1) {
            dfs(i); cout << ans + 1; return 0;
        }
    }
    return 0;
}