【Codeforces】Codeforces Round 866 (Div. 2) E.The Fox and the Complete Tree Traver | 树

标题链接

Problem – E – Codeforces

标题

标题粗心

在一棵有 $n$ 个节点的树上，狐狸能够从极点 $v$ 跳动到另一个极点 $u$ 当且仅当这些极点之间的间隔不超越 $2$。

换句话说，假如极点 $v$ 和 $u$ 之间有边直接相连，或者存在这样的极点 $w$ 使得极点 $v$ 和 $w$ 之间有边、极点 $u$ 和 $w$ 之间有边，狐狸就能够在一次跳动中从极点 $v$ 到达极点 $u$。

求树上是否有循环路线 v1,v2,…,vnv_1,v_2,…,v_nv1​,v2​,…,vn​ 使得：狐狸能够从极点 viv_ivi​ 跳到极点 vi+1v_{i+1}vi+1​，狐狸能够从极点 vnv_nvn​ 跳到极点 v1v_1v1​，且一切 viv_ivi​ 是成对不同的。

思路

简单通过手玩发现假如树上存在下图所示结构那么必定无解。

所以有解的树必定是一条链上挂着若干个叶子节点的结构。

我们首先要 check 整棵树是否是有解的形状，只需要将一切度为 $1$ 的节点删除，若剩余的节点不是一条链即无解，假如剩余的部分存在度大于 $2$ 的节点即可说明不是链。

在有解的情况下，一种合法的构造解的方案是：

首先将剩余的链拎出来，即用数组 $ans$ 顺序存储图中的橙色节点。

先正着遍历一遍 $ans$ 数组，遍历到第 $i$ 个节点时，若 $i$ 为奇数就输出橙色节点 $ans[i]$，不然输出节点 $i$ 上挂着的绿色节点。

再倒着遍历一遍 $ans$ 数组，遍历到第 $i$ 个节点时，若 $i$ 为偶数就输出橙色节点 $ans[i]$，不然输出节点 $i$ 上挂着的绿色节点。

上图的遍历成果如下所示。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int n,d[N],ans[N],tot;
vector<int>e[N],t;
int main()
{
	scanf("%d",&n);
	for (int x,y,i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
		d[x]++;
		d[y]++;
	}
	for (int i=1;i<=n;++i)
		if (d[i]==1) t.push_back(i),d[i]=0;
	for (auto i:t)
		for (auto v:e[i]) d[v]--;
	int id=1;
	for (int i=1;i<=n;++i)
	{
		if (d[i]==1) id=i;
		if (d[i]>2) return printf("No\n"),0;
	}
	printf("Yes\n");
	memset(d,0,sizeof(d));
	for (int i=id,fa=0,flg=1;flg;)
	{
		ans[++tot]=i;
		flg=0;
		for (auto v:e[i])
			if (v!=fa&&e[v].size()!=1)
			{
				fa=i;
				i=v;
				flg=1;
				break;
			}
	}
	for (int i=1;i<=tot;++i)
	{
		if (i&1) printf("%d ",ans[i]);
		else 
		{
			for (auto v:e[ans[i]])
				if (v!=ans[i-1]&&v!=ans[i+1]) printf("%d ",v);
		}
	}
	for (int i=tot;i>=1;--i)
	{
		if (i&1)
		{
			for (auto v:e[ans[i]])
				if (v!=ans[i-1]&&v!=ans[i+1]) printf("%d ",v);
		}
		else printf("%d ",ans[i]);
	}
	return 0;
}