1946C - Tree Cutting

CF难度：1600

从题意中看是一道比较经典的树形DP问题，题目要求的是把一棵树切k次，求被分割的树中最小的节点x的最大值是多少，因此可以采用二分写法，对于每一个树中，满足mid的节点个数是否等于k个。

题目链接：Tree Cutting

对于每个二分，都用一遍dfs遍历树，因此check函数可以这么写：

bool check(int mid){
	tot=0;
	int z=dfs(1,-1);//每次二分重新遍历一遍树
	if(z<mid)tot--;//最后还有ans，判断是否能分割树
	if(tot<k)return false;
	else return true;
}

dfs函数采用递归的写法，加入了ans，判断遍历到该节点是否能满足以该x为根节点形成的树的节点个数>=mid，如果可以，tot++；

int dfs(int x,int fa){
	int ans=1;
	for(const auto &y:g[x]){
		if(y==fa)continue;
		ans+=dfs(y,x);
	}
	if(ans>=mid){
		ans=0;
		tot++;
	}
	return ans;
}

注意建双向边

代码附上：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N =1e5+5;
vector<int>g[N];
int n,k,tot=0,mid;

int dfs(int x,int fa){//fa防止死循环
	int ans=1;
	for(const auto &y:g[x]){
		if(y==fa)continue;
		ans+=dfs(y,x);
	}
	if(ans>=mid){
		ans=0;
		tot++;
	}
	return ans;
}

bool check(int mid){
	tot=0;
	int z=dfs(1,-1);//每次二分重新遍历一遍树
	if(z<mid)tot--;//最后还有ans，判断是否能分割树
	if(tot<k)return false;
	else return true;
}

void solve(){
	cin>>n>>k;
	
	for(int i=1;i<=n;i++)g[i].clear();
	
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	int l=0,r=n+1;
	while(l<r){
		mid=(l+r+1)/2;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	
	cout<<l<<"\n";
	
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}