自动搬运

查看原文

来自洛谷，原作者为

	lmh .

搬运于2025-08-24 23:07:13，当前版本为作者最后更新于2025-01-01 12:16:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

参考了官方题解。

把拓扑序倒过来就是一个 dfs 序，容易发现这个 dfs 序上一个结点的父亲必须在它前面，没有其他限制。

拉出第一个 dfs 序来，设其为 ${1,2,\cdots,n}$。现在我们发现这里一个节点有多个可能的父亲，需要想办法把它们分开。

对于剩下的每条 dfs 序，考虑算出它的所有前缀最小值，发现这唯一确定了一条树上的链。所以可以对每个叶子做一次 dfs ，能得到大约 60 分。

实际上我们可以做得更好。考虑去掉叶子之后形成的树，对这棵树的每个叶子进行 dfs。考虑每个节点，在 dfs 到它的时候先搜原树上的叶子再搜其他邻居，这样就能算出每个叶子的父亲。

这样的话我们去掉所有叶子，剩下部分的叶子总数加上 $1$（最初的 dfs 序列）就是答案……吗？实际上对于非菊花图，剩余的叶子至少有两个，可以让一个作为第一个 dfs 序，这样可以再节省一个。

现在还有一个小问题，就是我们无法区分叶子节点的兄弟与父亲。这个是简单的，每次搜索完叶子之后打一个标记，让下一次以相反的顺序搜索即可。

然后就做完了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=107;
ll T,n,m,timer,a[N],deg[N];
ll ans[N][N];
vector<ll> to[N],tmp;
void dfs(int u,int fa){
	tmp.clear();
	ans[m][timer--]=u;
	for (auto v:to[u]) if (v!=fa&&to[v].size()==1) tmp.emplace_back(v);
	if (a[u]&&tmp.size()) reverse(tmp.begin(),tmp.end());a[u]^=1;
	for (auto v:tmp) ans[m][timer--]=v;
	for (auto v:to[u]) if (v!=fa&&to[v].size()>1) dfs(v,u);
}
void solve(){
	m=0;
	memset(deg,0,sizeof(deg));
	for (int i=1;i<N;++i) to[i].clear();
	cin>>n;
	for (int u,v,i=1;i<n;++i){
		cin>>u>>v;++deg[u];++deg[v];
		to[u].emplace_back(v);to[v].emplace_back(u);
	}
	for (int i=1;i<=n;++i) if (deg[i]==n-1){
		cout<<"2\n";
		for (int j=1;j<=n;++j) if (i!=j) cout<<j<<" ";cout<<i<<'\n';
		for (int j=n;j;--j) if (i!=j) cout<<j<<" ";cout<<i<<'\n';
		return;
	}
	memset(deg,0,sizeof(deg));
	for (int i=1;i<=n;++i) if (to[i].size()!=1){
		for (auto j:to[i]) deg[i]+=(to[j].size()>=2);
		if (deg[i]==1){
			++m;timer=n;
			dfs(i,0);
		}
	}
	cout<<m<<'\n';
	for (int i=1;i<=m;++i){
		for (int j=1;j<=n;++j) cout<<ans[i][j]<<' ';cout<<'\n';
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--) solve();
	return 0;
}