关于我赛时60pts竟然是因为我不知道树形背包是n^2的这件事

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
const int N=405,MOD=998244353;

int n;
vector<int> G[N];
int dep[N],cnt;
int fa[N];
int val[N],siz[N],res[N];
int dp[N][N];//在i子树里面删了j个点的最小代价
int tmp[N];

void dfs(int u)
{
	dep[u]=dep[fa[u]]+1;
	for(int v:G[u])
	{
		if(v==fa[u]) continue;
		fa[v]=u,dfs(v);
	}
}

void dfs2(int u)
{
	siz[u]=1,cnt++;
	memset(dp[u],0x3f,sizeof dp[u]);
	dp[u][0]=0;
	for(int v:G[u])
	{
		if(v==fa[u]||val[v]==0) continue;
		dfs2(v);
		memcpy(tmp,dp[u],sizeof dp[u]);
		for(int k1=1;k1<=cnt;k1++)
			for(int k2=0;k2+k1<=cnt;k2++)
				tmp[k2+k1]=min(dp[u][k2]+dp[v][k1],tmp[k2+k1]);
		for(int i=0;i<=n;i++) dp[u][i]=tmp[i];
		siz[u]+=siz[v];
		val[u]+=val[v];
	}
	dp[u][siz[u]]=val[u];
}

void solve()
{
	cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++)
  G[i].clear(),val[i]=fa[i]=siz[i]=dep[i]=res[i]=0;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	fa[1]=1,dfs(1);
	for(int i=1;i<=n;i++)
	{
		int now=i;
		while((dep[now]-1)*2>=dep[i]) 
			now=fa[now];
		val[now]++;
	}
	dfs2(1);
	for(int i=0;i<=cnt;i++)
		if(dp[1][i]<=n) res[n-dp[1][i]]=cnt-i;
	for(int i=n;i;i--)
	{
		if(res[i]) res[i]=n-res[i]+1;
		else res[i]=res[i+1];
	}
	for(int i=1;i<=n;i++) cout<<res[i]<<" ";
	cout<<'\n';
}

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

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
const int N=1e4+5,MOD=998244353;

int n;
vector<int> G[N];
int dep[N],cnt;
int fa[N];
int val[N],siz[N],res[N];
int dp[N][N];
int du[N];

void dfs(int u)
{
	dep[u]=dep[fa[u]]+1;
	for(int v:G[u])
	{
		if(v==fa[u]) continue;
		fa[v]=u,dfs(v);
	}
}

void dfs2(int u)
{
	siz[u]=0,cnt++,dp[u][0]=0;
	for(int v:G[u])
	{
		if(v==fa[u]||val[v]==0) continue;
		dfs2(v);
		for(int k2=siz[u];k2>=0;k2--)
			for(int k1=1;k1<=siz[v]&&k1+k2<=n;k1++)
				dp[u][k2+k1]=min(dp[u][k2]+dp[v][k1],dp[u][k2+k1]);
		siz[u]+=siz[v],val[u]+=val[v];
	}
	siz[u]++;
	dp[u][siz[u]]=val[u];
}

void solve()
{
	cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=n;j++)
			dp[i][j]=1e9;
	for(int i=1;i<=n;i++)
		G[i].clear(),val[i]=fa[i]=siz[i]=dep[i]=res[i]=du[i]=0;
	int mx=0;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
		du[u]++,du[v]++;
		mx=max(mx,max(du[u],du[v]));
	}
	fa[1]=1,dfs(1);
	for(int i=1;i<=n;i++)
	{
		int now=i;
		while((dep[now]-1)*2>=dep[i]) 
			now=fa[now];
		val[now]++;
	}
	dfs2(1);
	for(int i=0;i<siz[1];i++)
		if(dp[1][i]<=n) res[n-dp[1][i]]=cnt-i;
	for(int i=n;i;i--)
	{
		if(res[i]) res[i]=n-res[i]+1;
		else res[i]=res[i+1];
	}
	for(int i=1;i<=n;i++) cout<<res[i]<<" ";
	cout<<'\n';
}

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