楼下 $lzd$ 写的是不是太笼统了

我把怎么背包的展开讲讲？

首先我们发现有个中位数，然后我们就可以很套路得考虑二分，就是如果大于等于这个中位数，我们就设为1，反之为0

然后如果某一个值可以成为答案，当且仅当我把 $n-val+1$ 个1放进去以后至少有 $k$ 个合法的花。

然后我们发现这个二分非常弱智，因为我们不需要这个唐氏的二分。

我们可以直接树上 $DP$ 来跑我往里面丢若干个1，最多让多少朵花合法。

然后我们发现我们的1肯定是从根开始连续的一段子树。

然后就是经典的背包问题了。

感觉思路很好想，但是可能因为我太菜了，调了好久

我个人认为这道题有下位紫了

然后强烈谴责出题人，因为我的代码可以跑满 $n^2$ 的，但是最大的点 $11ms$ 说明出题人根本没有构造极限数据。

我预计里面最大的 $n$ 不超过1000

#include<bits/stdc++.h>
#define int short
#define N 10001
using namespace std;
int f[N][N],siz[N];
vector<int>G[N];
int res[N];
int route[N];
int dept;
void dfs(int x,int fa){
//	g[x][dep[x]]=1;
//	mxdep[x]=dep[x];
	route[++dept]=x;
	++f[route[(dept+1)/2]][1];
	for(int i=0; i<G[x].size(); i++){
		int y=G[x][i];
		if(y==fa)continue;
		dfs(y,x);
//		mxdep[x]=max(mxdep[x],mxdep[y]);
//		for(int j=dep[y]; j<=mxdep[y]; j++)g[x][j]+=g[y][j];
	}dept--;
	
}int n;
void dfs2(int x,int fa){
	siz[x]=1;
	f[x][0]=0;
	for(int i=0; i<G[x].size(); i++){
		int y=G[x][i];
		if(y==fa)continue;
		dfs2(y,x);
		for(int j=siz[x]; j>=1; j--){
			for(int k=0; k<=siz[y]; k++){
				f[x][j+k]=max(f[x][j+k],(short)(f[y][k]+f[x][j]));
			}
		}siz[x]+=siz[y];
	}
	if(x==1){
		for(int j=1; j<=siz[x]; j++){
//			cout<<f[x][j]<<" ";
			res[f[x][j]]=max(res[f[x][j]],(short)(n-j+1));
		}
//		cout<<endl;
	}
	
}
signed main(){
	freopen("blossom.in","r",stdin);
	freopen("blossom.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1; i<=n; i++)G[i].clear(),res[i]=0;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				f[i][j]=0;
			}
		}
		for(int i=1; i<n; i++){
			int x,y;scanf("%d%d",&x,&y);
			G[x].push_back(y),G[y].push_back(x);
		}
		dfs(1,1);
		dfs2(1,1);
		res[n+1]=0;
		for(int i=n; i>=1; i--)res[i]=max(res[i],res[i+1]);
		for(int i=1; i<=n; i++)printf("%d ",res[i]);
		printf("\n");
	}
	return 0;
}