CF1042F Leaf Sets [DFS/贪心]

ajcxsu
ajcxsu 2018年09月18日
  • 87 次阅读

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://acxblog.site/archives/sol-cf-1042f.html
本文采用 CC BY-NC-SA 3.0 协议进行许可