前置芝士：启发式合并，树上背包。
思路
首先我们要在 \(1\) 上填写 \(n\)，因为 \(1\) 如果不填 \(n\) 的话，所有权值都一定会 \(\le n\)。
然后就是如何往下继续填了。
首先，感受到盛开度应该从大往小了从浅往深填，所有的答案不会低于 \(\lceil \frac n2\rceil\)。然后我们发现这样填一定不劣：因为如果对答案有影响的盛开度交换的话，那么原本更大的中位数能作为答案的节点会向下移动，有可能因为超出子树中的最大深度而减少；对答案没有影响的不用讨论。
根据这种填法，我们来考虑每个节点能作为多少个节点的中位数。因为是从上往下从大往小了填的，所以当当前节点深度为 \(dep\) 时能造成影响的节点，只会是在该节点子树中的，深度为 \([2dep-1,2dep]\) 的节点个数，不妨称为 \(val\)。
我们来维护这个东西，不妨使用 map 记录每个节点的子树中不同深度的节点的个数分别是多少。
注意到 \(n\le 10^4\)，所以我们不能直接暴力合并，因为 map 自身带一个 \(\log\)，暴力合并的时间复杂度为 \(O(n^2 \log n)\)。因此考虑启发式合并，将小的合并到大的里面去。就这样，我们在 \(O(n\log^2 n)\) 的时间复杂度下解决了这一步。
接下来，我们统计答案。因为我们要从上往下填，那么一个节点的答案能被统计，其到根节点的路径一定都要被填上盛开度。因此变为一个树上背包问题。我们设 \(f_{u,i}\) 为以 \(u\) 为根的子树影响了 \(i\) 个节点的中位数时，以该节点为根的子树最小填写的盛开度的个数。那么我们首先将 \(f_u\) 复制到 \(f_u'\)，此时有转移 $f_{u,i+j}'\gets f_{u,i}+f_{v,j} $，其中 \(v\) 为 \(u\) 的子节点，\(i,j\) 分别为 \(u,v\) 当前可以计算到的最大影响的中位数的个数。我们发现我们的转移为以 \(u\) 为根子树恰好影响了 \(i\) 个节点的中位数时，以该节点为根的子树最小填写的盛开度的个数，所以我们还要取一个后缀 \(\min\)。
一种错误的统计答案的方式
对于每个节点，类似拓扑的方法去更新，将可以改变节点个数最多的放在前面，并优先处理。
反例：
注意到我们不可能开一个 dp[10100][10100]，所以我们使用 vector 完成转移。该部分时间复杂度 \(O(n^2)\)，但是常数很小，且 \(n\le 10^4\)，可以通过。
呃啊这种题的题解怎么这么难写。
时间复杂度：\(O(n^2)\)。
难点/坑点：
点击查看代码
#include<bits/stdc++.h>#define pii pair<int,int>
#define pll pair<long long,long long>
#define ll long long
#define i128 __int128#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define in4(a,b,c,d) a=read(), b=read(), c=read(), d=read()
#define fst first
#define scd second
#define dbg puts("IAKIOI")using namespace std;int read() {int x=0,f=1; char c=getchar();for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }#define maxn 10050int n,dep[maxn];
vector<int> G[maxn];
map<int,int> mp[maxn];
vector<int> f[maxn];
int ans[maxn]; bool vis[maxn];
int fin[maxn],sum[maxn];void dfs1(int u,int dis,int fa) {dep[u]=dis; mp[u][dis]++; sum[u]=0;for(auto v:G[u]) if(v!=fa) {dfs1(v,dis+1,u); sum[u]+=sum[v];if(mp[u].size()<mp[v].size()) swap(mp[u],mp[v]);for(auto [x,y]:mp[v]) mp[u][x]+=y;}int res=mp[u][dis*2]+mp[u][dis*2-1];sum[u]+=res;
// cout<<u<<' '<<dis<<' '<<res<<'\n';ans[u]=(res);
}void dfs2(int u,int fa) {if(!ans[u]) return ;f[u].clear();f[u].push_back(1e9);For(i,1,ans[u]) f[u].push_back(1);For(i,ans[u]+1,sum[u]) f[u].push_back(0);for(auto v:G[u]) if(v!=fa) {dfs2(v,u); if(!f[v].size()) continue;vector<int> qwq; qwq.clear();qwq=f[u];For(i,1,ans[u]) if(f[u][i]!=0) { For(j,1,ans[v]) if(f[v][j]!=0) {
// cout<<j+i<<'\n';if(qwq[j+i]!=0) qwq[i+j]=min(qwq[i+j],f[v][j]+f[u][i]);else qwq[i+j]=f[v][j]+f[u][i];}}f[u]=qwq;ans[u]+=ans[v];}Rep(i,ans[u]-1,1) f[u][i]=min(f[u][i+1],f[u][i]);
// cout<<u<<":";
// For(i,1,ans[u]) cout<<f[u][i]<<' '; puts("");
}void work() {in1(n); For(i,2,n) {int u,v; in2(u,v);G[u].push_back(v),G[v].push_back(u);}dfs1(1,1,0);dfs2(1,0);int mn=1e9;Rep(i,n,1) {mn=min(mn,f[1][i]);fin[i]=mn;}For(i,1,n) cout<<n-fin[i]+1<<' ';puts("");For(i,1,n) G[i].clear(),ans[i]=0,mp[i].clear(),dep[i]=0,vis[i]=0;
}signed main() {
// freopen("data.in","r",stdin);
// freopen("myans.out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);double stt=clock();int _=1;_=read();
// cin>>_;For(i,1,_) {work();}cerr<<"\nTotal Time is:"<<(clock()-stt)*1.0/1000<<" second(s)."<<'\n';return 0;
}