题解 CF1042F 【Leaf Sets】

#### 题目大意 给定一棵树，把树的叶子分成多个集合，要求每个集合的叶子距离不超过$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; } ```