Ccodeforce刷题日记
![CodeForce[1500-2000]——1946C Tree Cutting,算法,c++,c语言,codeforce,数据结构,树,深度优先](https://imgs.yssmx.com/Uploads/2024/04/855712-1.png)
题目大意：给你一个n个节点的树，将树的k条边移除，剩下的最小的联通块的节点数量为x，现在要求出x的最大值。文章来源：https://www.toymoban.com/news/detail-855712.html
思路：求最小值的最大，很容易想到二分法，二分最小联通块的节点数x，利用dfs将树分块，当块数量达到x时就分下一组，如果最后一组没达到x，就组数+1，让最后一组和到前面的组中，再利用组数和k比较，进行二分判断。文章来源地址https://www.toymoban.com/news/detail-855712.html
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int t,n,k,tot=0,mid;
vector<int>e[maxn];
int dfs(int u,int fa){
int ans=1;
for(const auto &v:e[u]){
if(v==fa) continue;
ans+=dfs(v,u);
}
if(ans>=mid){
ans=0;tot++;
}
return ans;
}
bool check(int mid){
tot=0;
int z=dfs(1,-1);
if(z<mid) tot--;
if(tot<k) return false;
else return true;
}
int main(){
cin>>t;
while(t--){
cin>>n>>k;
for(int i=1;i<=n;i++)e[i].clear();
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
e[u].push_back(v);e[v].push_back(u);
}
int l=0,r=n+1;
while(l<r){
mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
return 0;
}到了这里，关于CodeForce[1500-2000]——1946C Tree Cutting的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
