自动搬运

查看原文

来自洛谷，原作者为

	zzxLLL Retired

搬运于2025-08-24 21:55:28，当前版本为作者最后更新于2023-08-24 08:49:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

挺有意思一道题。提供一种更方便理解(?)的做法。

要求字典序最小，我们可以贪心地确定第一个数，即满足度数 $\leq 2$ 的编号最小的节点。

设这个节点为 $u$，将 $u$ 钦定为最左边的节点，先讨论 $u$ 度数为 $2$ 的情况，那么与他相连的两个节点，一个是右儿子 $v$，一个是父亲 $f$。

先不考虑字典序最小。

此时我建出一颗新的树，$u$ 为根节点，让 $v$ 为 $u$ 的左儿子，$f$ 为 $u$ 的右儿子，其余的关系不变。若将在 $u$ 处的遍历顺序设置为前序遍历，那么在 $u$ 处就会按照 $u - v - w$ 的顺序遍历。那么在 $u$ 处这其实和原树的遍历顺序是相同的。

回到原树，$v$ 是 $u$ 的儿子，那么在 $v$ 的子树中应该是中序遍历，这点在新树上也一样，故新树上 $v$ 及其子树都采取中序遍历。

而 $f$ 是 $u$ 的父亲，当原树遍历完 $u$ 和 $v$ 的子树之后，它们就不影响后面的中序遍历的，可以删去。删去之后，$f$ 的情况就和 $u$ 相同了，即都被钦定为最左边的节点。这是一个子问题，让 $f$ 成为新的 $u$，递归解决。

再是度数为 $1$ 的情况，与 $u$ 相连的节点为 $w$，那么 $w$ 成为新树上 $u$ 的左儿子，在原树上 $w$ 就是 $u$ 的右儿子；$w$ 成为新树上 $u$ 的右儿子，在原树上 $w$ 就是 $u$ 的父亲。

所以总的策略就是：先将 $u$ 提为根节点；然后新树按照如下规则 dfs：

• 若当前节点采用前序遍历，那么其左儿子采用中序遍历，右儿子采用前序遍历

• 若当前节点采用中序遍历，那么其左右儿子都采用中序遍历。

可以证明这样形成的遍历序列就是原树的中序遍历序列。

下面考虑怎么使字典序更小。即如何安排新树上的左右儿子。

先以 $u$ 为根，求出 $dp_x$ 为 $x$ 的子树内度数 $\leq 2$ 的编号最小的节点编号。

然后 dfs 过程中分类讨论，当前节点为 $x$：

1. $x$ 处为前序遍历

若新树上 $x$ 有 $1$ 个儿子 $s$，那么如果 $dp_s < s$ 就将 $s$ 作为新树上 $x$ 的左儿子，否则作为 $x$ 的右儿子。

若新树上 $x$ 有 $2$ 个儿子 $s_1, s_2$，那么如果 $dp_{s_1} < dp_{s_2}$ 那么将 $s_1$ 作为新树上 $x$ 的左儿子，$s_2$ 作为 $x$ 的右儿子。否则 $s_2$ 作为左儿子，$s_1$ 作为右儿子。

2. $x$ 处为中序遍历

若新树上 $x$ 有 $1$ 个儿子 $s$，那么如果 $dp_s < x$ 就将 $s$ 作为 $x$ 的左儿子，否则作为 $x$ 的右儿子。

若新树上 $x$ 有 $2$ 个儿子 $s_1, s_2$，那么如果 $dp_{s_1} < dp_{s_2}$ 则将 $s_1$ 作为新树上 $x$ 的左儿子，$s_2$ 为右儿子。否则 $s_2$ 为左儿子，$s_1$ 为右儿子。

容易证明这样贪心是正确的。按照顺序输出即可。

#include<cstdio>
#include<vector>
#include<algorithm>
const int M=1e6+10;
const int inf=1e9+7;

int n,rt,deg[M],f[M];
std::vector<int>g[M];

void dfs(int u,int fa,bool type){
	// type = 0 : 前序遍历
	// type = 1 : 中序遍历
	std::vector<int>nxt;
	for(int v:g[u])
		if(v!=fa) nxt.push_back(v);
	if(!type){
		// 根 - 左子树 - 右子树
		printf("%d ",u);
		if(nxt.size()==1){
			if(f[nxt[0]]<nxt[0]){
				dfs(nxt[0],u,1);
			}else{
				dfs(nxt[0],u,0);
			}
		}else if(nxt.size()==2){
			if(f[nxt[0]]<f[nxt[1]]){
				dfs(nxt[0],u,1);
				dfs(nxt[1],u,0);
			}else{
				dfs(nxt[1],u,1);
				dfs(nxt[0],u,0);
			}
		}
	}else{
		// 左子树 - 根 - 右子树
		if(nxt.size()==0){
			printf("%d ",u);
		}else if(nxt.size()==1){
			if(f[nxt[0]]<u){
				dfs(nxt[0],u,1);
				printf("%d ",u);
			}else{
				printf("%d ",u);
				dfs(nxt[0],u,1);
			}
		}else if(nxt.size()==2){
			if(f[nxt[0]]<f[nxt[1]]){
				dfs(nxt[0],u,1);
				printf("%d ",u);
				dfs(nxt[1],u,1);
			}else{
				dfs(nxt[1],u,1);
				printf("%d ",u);
				dfs(nxt[0],u,1);
			}
		}
	}
}

void dp(int u,int fa){
	f[u]=(deg[u]<=2?u:inf);
	for(int v:g[u]){
		if(v==fa) continue;
		dp(v,u);
		f[u]=std::min(f[u],f[v]);
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&deg[i]);
		for(int j=1,x;j<=deg[i];j++){
			scanf("%d",&x);
			g[i].push_back(x);
		}
		if(deg[i]<=2&&!rt) rt=i;
	}
	dp(rt,0);
	dfs(rt,0,0);
	return 0;
}