题解 CF1042F 【Leaf Sets】

2018-09-25 11:17:01


题目大意

给定一棵树,把树的叶子分成多个集合,要求每个集合的叶子距离不超过 $k$,问最少可以划分成几个集合

题解

感觉思路挺神仙的……

贪心的思想,按深度处理每个点,记录每个点的子树里的叶子节点到ta的距离,排个序后把相邻的相加不大于 $k$的划成一个集合,即从 $1$开始的一段区间,其他的各自搞个集合,然后返回大集合里的最长边,ta上面的节点处理这棵子树时就以这条边为代替了

为什么这样划分保证最优呢?假设有三条边 $a,b,c(a<b<c)$,且 $a+b\leq k,a+c\leq k,b+c>k$,如果 $a$和 $c$放一个集合里,那这个集合就不能放 $b$了,同时这个集合能加进去的长度为 $k-c$,如果放 $b$,这个集合能加进去的长度为 $k-b$,明显是优于放 $c$的

那么为什么是返回大集合里的最长边呢?如果返回其他单元素的集合,ta们肯定大于大集合里的最长边,其他子树与ta匹配的限制会变大,所以可能会划分成更多的集合,不是更优的处理

代码

# include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+1;
struct p{
    int x,y;
}c[MAX<<1];
int n,k,num,ans;
int du[MAX],h[MAX];
void add(int x,int y)
{
    c[++num]=(p){h[x],y},h[x]=num;
    c[++num]=(p){h[y],x},h[y]=num;
}
int dfs(int x,int f=0)
{
    if(du[x]==1) return 0;
    vector<int> ve;
    for(int i=h[x];i;i=c[i].x)
      if(c[i].y!=f) ve.push_back(dfs(c[i].y,x)+1);
    sort(ve.begin(),ve.end());
    int L=ve.size()-1;
    for(;L>=1;--L)
      {
        if(ve[L]+ve[L-1]<=k) break;
        ++ans;
      }
    return ve[L];
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1,x,y;i<n;++i)
      scanf("%d%d",&x,&y),add(x,y),++du[x],++du[y];
    int rt=1;
    for(int i=1;i<=n;++i)
      if(du[i]>1) {rt=i;break;}
    dfs(rt);
    return printf("%d",ans+1),0;
}