Codeforces Round 936 (Div. 2)

C. Tree Cutting

题意：给定一棵树，需要删除 k 条边，使得 k+1 个联通块中的最小结点数最大。求出这个最大值

思路：求最小值最大--想到二分答案--然后深搜满足条件的连通块是否大于k即可

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<int>v[N];
int n,k,cnt;
dfs(int u,int father,int mid)
{//返回的是每个子树节点的个数 若有子树节点符合mid 则切一刀 返回0int res=1;//自身的节点个数为1 从上到下 从下返回 记录节点个数for(int i=0;i<v[u].size();i++){int j=v[u][i];if(j==father) continue;//如果是自己的父亲节点就不深搜下取res+=dfs(j,u,mid);}if(res>=mid){res=0;cnt++;}return res;
}
bool check(int mid)
{cnt=0;dfs(1,0,mid);if(cnt>k) return true;return false;
}
int main()
{int t;cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++) v[i].clear();for(int i=1;i<n;i++){int a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}int l=0,r=n+1;while(l<r){int mid=(l+r+1)>>1;if(check(mid)) l=mid;else r=mid-1;}cout<<l<<endl;}return 0;
}