自动搬运

查看原文

来自洛谷，原作者为

	A_zjzj AFO：2019.9~2025.01.22

搬运于2025-08-24 21:50:05，当前版本为作者最后更新于2023-01-17 23:27:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

其他题解都是大码量的直接构造，来一发 dp 的题解。

思路很明确，直接 dp，然后输出路径即可。

考虑先把 $1\to n$ 的路径找出来，记为 $a_i(1\le i\le m)$。

那么肯定存在一种路径依次经过这些点的子树，然后遍历完 $a_i$ 的子树后再遍历 $a_{i+1}$ 的子树。

这样的话，每个 $a_i$ 的子树就各自独立了，所以分别对每个子树进行求解。

遍历子树

由于每次最多只能跳 $2$ 步，所以如果要遍历 $u$ 的子树内的所有点，那么只有以下几种情况：

• 先到 $u$，然后从 $u$ 跳出去（当且仅当 $u$ 为叶子节点时可以）；

• 先到 $u$，然后从 $u$ 的某个儿子跳出去；

• 先到 $u$ 的某个儿子，然后从 $u$ 的某个儿子跳出去；

• 先到 $u$ 的某个儿子，然后从 $u$ 跳出去。

观察这些情况，发现第二种和第四种本质上是一样的，无非就是遍历顺序正反而已，先合并为一种。

于是，设 $f_{u,i=0/1/2}$ 分别为上述的第 $i+1$ 中情况是否可行。

考虑如何转移：

$f_{u,0}=[u\ is\ \texttt{leaf}];$

$f_{u,1}$ 至多可以先跳到一个非叶子的儿子遍历，最后停在这个儿子，接着跳到其他的叶子的儿子。

即 $f_{u,1}=\operatorname{and}_{v\in son(u)}f_{v,0}/f_{v,1}$，其中只能有一个 $f_{v,1}$。

所以转移就是：

f[u][1]=1;
int t1=0;
for(int v:A[u])if(v^fa&&!vis[v]){
	dfs(v,u);
	if(!f[v][0])
		if(!f[v][1])f[u][1]=0;
		else if(++t1>1)f[u][1]=0;
}

$f_{u,2}$ 的话就是要有两个儿子可以先到 $v$，再从 $v$ 的儿子跳出或先到 $v$ 的儿子再从 $v$ 跳出（两个儿子的遍历顺序决定了是属于第二种还是第四种，先遍历到的选择第二种，后遍历到的选择第四种）。

转移如下：

f[u][2]=1;
int t2=0;
for(int v:A[u])if(v^fa&&!vis[v]){
	dfs(v,u);
	if(!f[v][0])
		if(!f[v][1])f[u][2]=0;
		else if(++t2>2)f[u][2]=0;
}

这样 $f$ 就可以 $O(n)$ 完成转移了。

遍历 $1\to n$ 的链

设 $g_{i,0/1}$ 表示 $a_i$ 的子树遍历完之后，在 $u$ 或 $u$ 的某个儿子，是否可行。

这样就很简单了，枚举 $a_i$ 和 $a_{i+1}$ 的状态，选择合适的 $f_{a_{i+1}}$ 进行转移即可。

转移见代码，其实并不难，复杂度也是 $O(n)$。

总结

至此，我们已经完成了 $f,g$ 的转移，判断有解无解，然后按照转移的方式输出 dp 的路径即可。

具体实现见代码，总复杂度：$O(n)$。

代码

#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=5e5+10;
int n,m,top,a[N],stk[N],vis[N],f[N][3],g[N][2];vector<int>ans,A[N];
void add(int u,int v){A[u].push_back(v);A[v].push_back(u);}
void find(int u,int fa=0){
	stk[++top]=u;if(u==n)copy(stk+1,stk+1+top,a+1),m=top;
	for(int v:A[u])if(v^fa)find(v,u);stk[top--]=0;
}
void dfs(int u,int fa=0){
	f[u][0]=f[u][1]=f[u][2]=1;
	int t=0,t1=0,t2=0;
	for(int v:A[u])if(v^fa&&!vis[v]){//f 的转移
		t++;dfs(v,u);
		if(!f[v][0])if(!f[v][1])f[u][1]=0;else if(++t1>1)f[u][1]=0;
		if(!f[v][0])if(!f[v][1])f[u][2]=0;else if(++t2>2)f[u][2]=0;
	}
	if(t)f[u][0]=0;else f[u][1]=f[u][2]=0;//特判叶子节点
}
void findf(int u,int i,int fa=0){
	if(!i){
		ans.push_back(u);//叶子节点
	}
	else if(i==1){//u 开始,v 结束
		ans.push_back(u);//因为是 u 开始,所以直接把 u 扔进去就好了
		for(int v:A[u])if(v^fa&&!vis[v]){//先遍历非叶子
			if(!f[v][0])findf(v,3,u);
		}
		for(int v:A[u])if(v^fa&&!vis[v]){//再遍历叶子
			if(f[v][0])findf(v,0,u);
		}
	}
	else if(i==2){//v 开始,v' 结束
		int t=0;
		for(int v:A[u])if(v^fa&&!vis[v]){
			if(!f[v][0])t++;
		}
		if(t==1)return findf(u,1,fa);//必须要找到两个不同的 v 和 v',否则就是第 2 种情况
		t=0;
		for(int v:A[u])if(v^fa&&!vis[v]){
			if(!f[v][0]){
				if(!t)findf(v,1,u),ans.push_back(u),t++;
				else findf(v,3,u);
				//第一个 v 先到 v,再到儿子
				//第二个 v' 先到儿子，再到 v'
			}
		}
		for(int v:A[u])if(v^fa&&!vis[v]){
			if(f[v][0])findf(v,0,u);//最后遍历叶子节点
		}
	}else{//与情况 2 类似,倒着做就好了
		for(int v:A[u])if(v^fa&&!vis[v]){
			if(f[v][0])findf(v,0,u);
		}
		for(int v:A[u])if(v^fa&&!vis[v]){
			if(!f[v][0])findf(v,1,u);
		}
		ans.push_back(u);
	}
}
void findg(int i,int j){//g 的路径输出
	if(i==1){
		findf(i,j);
		return;
	}
	int u=a[i];
	if(j==0){//直接照搬转移的方程即可
		if(g[i-1][0]&f[u][0])return findg(i-1,0),findf(u,0);
		if(g[i-1][0]&f[u][1])return findg(i-1,0),findf(u,3);
		findg(i-1,1);findf(u,0);
	}else{
		if(g[i-1][0]&f[u][1])return findg(i-1,0),findf(u,1);
		if(g[i-1][0]&f[u][2])return findg(i-1,0),findf(u,2);
		findg(i-1,1);findf(u,1);
	}
}
int main(){
	scanf("%d",&n);for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),add(u,v);
	find(1);for(int i=1;i<=m;i++)vis[a[i]]=1;for(int i=1;i<=m;i++)dfs(a[i]);
	g[1][0]=f[1][0];g[1][1]=f[1][1];//g 的初始化
	for(int i=2,u;u=a[i],i<=m;i++){//g 的转移
		g[i][0]|=g[i-1][0]&(f[u][0]|f[u][1]);
		g[i][0]|=g[i-1][1]&f[u][0];
		g[i][1]|=g[i-1][0]&(f[u][1]|f[u][2]);
		g[i][1]|=g[i-1][1]&f[u][1];
	}
	if(!g[m][0])return puts("BRAK"),0;//注意最后要落在 n，所以 g[m][1] 没有用
	findg(m,0);
	for(int x:ans)printf("%d\n",x);
	return 0;
}

谢谢您的阅读，有问题请指出