C. Tree Cutting

題意：給定一棵樹，需要刪除 k?條邊，使得 k+1?個聯(lián)通塊中的最小結(jié)點數(shù)最大。求出這個最大值

思路：求最小值最大--想到二分答案--然后深搜滿足條件的連通塊是否大于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)
{//返回的是每個子樹節(jié)點的個數(shù) 若有子樹節(jié)點符合mid 則切一刀 返回0int res=1;//自身的節(jié)點個數(shù)為1 從上到下 從下返回 記錄節(jié)點個數(shù)for(int i=0;i<v[u].size();i++){int j=v[u][i];if(j==father) continue;//如果是自己的父親節(jié)點就不深搜下取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;
}