CodeForce[1500-2000]——1946C Tree Cutting

Ccodeforce刷题日记

题目大意：给你一个n个节点的树，将树的k条边移除，剩下的最小的联通块的节点数量为x，现在要求出x的最大值。

思路：求最小值的最大，很容易想到二分法，二分最小联通块的节点数x，利用dfs将树分块，当块数量达到x时就分下一组，如果最后一组没达到x，就组数+1，让最后一组和到前面的组中，再利用组数和k比较，进行二分判断。

#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;
}