Problem

给定一棵树，将叶子节点分为数个集合使集合里点对最长距离不超过 $k$，求最少集合数。

Solution

考虑从下向上维护。

假设维护上来子树叶子节点的目前为止分成了 $k$ 个集合，并且每个集合的最深深度为 $k_i$，我们考虑如何合并这 $k$ 个集合。

我们可以证明，假设有 $k_1< k_2< ... < k_n$，则我们找到最大的 $i$ 使 $k_i+k_{i+1}>K$，那么 $k_1$ 到 $k_i$ 都可以合并在一起，并且这么合并一定最优。

若存在 $1,2,4$ 能合并，则一定有 $1,2,3$ 能合并，那么无论怎么合并，最后剩下来的一定会包含 $3,4$。

若存在 $1,2,4,6$ 能合并，则一定有 $1,2,3,4,6$ 能合并，所以所有的其它情况都可转化成上面的情况。

所以如此合并得到的结果最终是相同的。

此时上可并堆就可以做到 $O(n\log n)$ 的复杂度了。

进一步分析。若 $k_i+k_{i+1}>K$，那么在向上维护的过程中，$k_{i+1}$ 一定不会再与其它集合进行合并。

又因为所有比 $k_i$ 小的都已经合并，所以我们只需要得到 $k_i$ 即可，而令 $k_{i+1}$ 到 $k_n$ 直接单独成为集合。

于是只需用一个变量维护 $k_i$ 的值即可，这样的复杂度为 $O(n)$。

注意所有 $k_i>K$ 的情况。

Code

// Code by ajcxsu
// Problem: leaf sets

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10, M=2e6+10;
int h[N], to[M], nexp[M], d[N], p=1;
inline void ins(int a, int b) {
    nexp[p]=h[a], h[a]=p, to[p]=b, p++; d[a]++;
}

template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}


int k, ans;
int dfs(int x, int fa) {
    if(d[x]==1) return 1;
    int na=0;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fa) {
            int d=dfs(to[u], x);
            if(d+na>k) ans++, na=min(na, d);
            else if(d>na) na=d;
        }
    return na?na+1:0;
}

int main() {
    int n, u, v, x;
    gn(n), gn(k);
    for(int i=0;i<n-1;i++) gn(u), gn(v), ins(u, v), ins(v, u);
    for(int i=1;i<=n;i++) if(d[i]>1) x=dfs(i, 0), printf("%d\n", ans+bool(x)), exit(0);
    printf("%d\n", ans+1);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-cf-1042f.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆