MnZn求hack

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int T,n,dep[N],f[N][30],dp,tr[N],lg[N],l[N][N];
vector<int> v[N];
priority_queue<pair<int,int> > q;
int find(int i)
{
	return i & -i;
}
void dfs(int x,int deep,int fa)
{
	dep[x]=deep,f[x][0]=fa,dp=max(dp,deep);
	for(register int i=0;i<v[x].size();++i)
	{
		int to=v[x][i];
		if(to==fa) continue;
		dfs(to,deep+1,x);
	}
}
void serve(int now)
{
	if(now!=1)
	{
		int sd=dep[now]/2;
		int t=lg[sd],mid=now;
		while(sd>0)
		{
			if(sd>=(1<<t)) mid=f[mid][t],sd-=(1<<t);
			t--;
		}
		tr[mid]++;
	}
	for(register int i=0;i<v[now].size();++i)
	{
		int to=v[now][i];
		if(to==f[now][0]) continue;
		serve(to);
	}
}
void flower(int x)
{
	l[x][1]=tr[x];
	for(register int i=0;i<v[x].size();++i)
	{
		int to=v[x][i];
		if(to==f[x][0]) continue;
		flower(to);
		for(register int j=2;j<=n;++j)
			if(l[to][j-1]!=0) l[x][j]=max(l[x][j],l[to][j-1]+tr[x]);
	}
}
int main()
{
	cin>>T;
	for(register int i=2;i<=N;++i)
	{
		lg[i]=lg[i-1];
		if(i==find(i)) lg[i]++;
	}
	while(T--)
	{
		cin>>n;
		for(register int i=1;i<n;++i)
		{
			int x,y;
			cin>>x>>y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(1,1,0);
		for(register int i=1;(1<<i)<dp;++i)
			for(register int j=1;j<=n;++j)
				f[j][i]=f[f[j][i-1]][i-1];
		tr[1]++; serve(1); flower(1); 
		int num=n;
		for(register int i=1;i<=n;++i)
		{
			int st=l[1][i-1]+1;
			if(l[1][i]==0) l[1][i]=n;
			for(register int j=st;j<=l[1][i];++j) cout<<num<<" ";
			if(l[1][i]==n) break;
			num--;
		}
		cout<<endl;
		for(register int i=1;i<=n+1;++i) 
		{
			for(register int j=0;j<30;++j) f[i][j]=0;
			for(register int j=0;j<=n;++j) l[i][j]=0;
			dep[i]=0,tr[i]=0;
			v[i].clear();
		}
		dp=0;
	}
	return 0;
}