楼下 $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;
}

树上背包复杂度 $\Theta(n^2)$

使用 #define int short 把空间卡到 256Mib 以内即可。

#include<bits/stdc++.h>
#define int short
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e>'9'||e<'0') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=10005;
int T,n;
vector<int>G[N];
int depth,mp[N],val[N];
int siz[N],dp[N][N];
int ans[N];
void dfs(int u,int f){
	mp[++depth]=u;
	++val[mp[(depth+1)/2]];
	for(auto v:G[u]){
		if(v==f)continue;
		dfs(v,u);
	}
	--depth;
}
void DP(int u,int f){
	siz[u]=1;
	dp[u][0]=0,dp[u][1]=val[u];
	for(auto v:G[u]){
		if(v==f)continue;
		DP(v,u);
		for(int i=siz[u];i>=1;--i){
			for(int j=0;j<=siz[v]&&i+j<=n;++j){
				dp[u][i+j]=max(dp[u][i+j],(short)(dp[u][i]+dp[v][j]));
			}
		}
		siz[u]+=siz[v];
	}
}
signed main() {
	freopen("blossom.in","r",stdin);
	freopen("blossom.out","w",stdout);
	R(T);
	while(T--) {
		R(n);
		for(int i=1; i<=n; ++i) {
			G[i].clear();
		}
		memset(val,0,sizeof val);
		memset(siz,0,sizeof siz);
		for(int i=1;i<=n;++i){
			for(int j=0;j<=n;++j){
				dp[i][j]=0;
			}
		}
		depth=0;
		for(int i=1,u,v; i<n; ++i) {
			R(u),R(v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		dfs(1,-1);
		DP(1,-1);
		for(int i=1; i<=n; ++i) {
			for(int k=dp[1][i-1]+1; k<=dp[1][i]; ++k) {
				ans[k]=n-i+1;
			}
		}
		for(int i=1;i<=n;++i){
			cout<<ans[i]<<" ";
		} 
		cout<<"\n";
	}

	return 0;
}