前言

还是一道神仙题

很难想

题面

luogu上copy的

样例解释懒得翻，我觉得应该都看得懂样例吧。

题面翻译

现有一棵 \(n\) 个点的形态未知的树，给定其长度为 \(2n-1\) 的欧拉序的一部分

请根据给出的残缺的欧拉序还原出一个完整的欧拉序或判断不存在这样的树

输入中用非零数字表示欧拉序被确定了，而 \(0\) 表示这位没有被确定

\(n\le 5\times 10^5\)

简化题意

现在给你一个欧拉序，有一些位置没有确定。现在让你判断是否存在这样的合法的欧拉序，如果有，就要输出一种合法方案。

题目描述

Euler is a little, cute squirrel. When the autumn comes, he collects some reserves for winter. The interesting fact is that Euler likes to collect acorns in a specific way. A tree can be described as $ n $ acorns connected by $ n - 1 $ branches, such that there is exactly one way between each pair of acorns. Let's enumerate the acorns from $ 1 $ to $ n $ .

The squirrel chooses one acorn (not necessary with number $ 1 $ ) as a start, and visits them in a way called "Euler tour" (see notes), collecting each acorn when he visits it for the last time.

Today morning Kate was observing Euler. She took a sheet of paper and wrote down consecutive indices of acorns on his path. Unfortunately, during her way to home it started raining and some of numbers became illegible. Now the girl is very sad, because she has to present the observations to her teacher.

"Maybe if I guess the lacking numbers, I'll be able to do it!" she thought. Help her and restore any valid Euler tour of some tree or tell that she must have made a mistake.

输入格式

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 5 \cdot 10^5 $ ), denoting the number of acorns in the tree.

The second line contains $ 2n - 1 $ integers $ a_1, a_2, \ldots, a_{2n-1} $ ( $ 0 \leq a_i \leq n $ ) — the Euler tour of the tree that Kate wrote down. $ 0 $ means an illegible number, which has to be guessed.

输出格式

If there is no Euler tour satisfying the given description, output "no" in the first line.

Otherwise, on the first line output "yes", and then in the second line print the Euler tour which satisfy the given description.

Any valid Euler tour will be accepted, since the teacher doesn't know how exactly the initial tree looks.

样例 #1

样例输入 #1

2
1 0 0

样例输出 #1

yes
1 2 1

样例 #2

样例输入 #2

4
1 0 3 2 0 0 0

样例输出 #2

yes
1 4 3 2 3 4 1

样例 #3

样例输入 #3

5
0 1 2 3 4 1 0 0 0

样例输出 #3

no

提示

An Euler tour of a tree with $ n $ acorns is a sequence of $ 2n - 1 $ indices of acorns. such that each acorn occurs at least once, the first and the last acorns are same and each two consecutive acorns are directly connected with a branch.

解法

这道题便思路 首先我们想一下欧拉序(我们用\(a\)表示)是怎么样的：

1. \(a_1 = a_{2n - 1}\)
2. \(\forall a_l = a_r, 2 | r - l(即是偶数),且出现了\frac{r - l}{2} + 1\)
   这一点自己举几个例子应该可以马上理解
3. 所有 $a_l = a_r $ 的区间构成的集合 \(S\)，\(S\) 必然可以构造出纯的构造关系，不可能存在 $ i ≠ j $
4. \(\forall 1\leq i\leq2n-1,1\leq a_i \leq n\)

现在我们不妨设有一个区间\([l, r]\), 因为满足\(a^{'}_l = a ^{'} _r\)的区间就一定代表了一颗子树，所以我们不妨先递归处理以后再用缩点的思想，缩成一个点，这一个序列变成了\(a^{''}_l\),就可以继续了。

对于每一个\(i\), 我们预处理出下一个和\(a_i\)相等的下标，也就是右端点，这样我们在缩点的时候可以顺面判断一下条件3，就是包含关系那个。

现在\([l, r]\) 就不存在权值相同的点，如果出现了少于\(\frac{r - l}{2} + 1\)种，我们就直接暴力填最前面。一个非常显然的是，种类数目超过\(\frac{r - l}{2} + 1\)种肯定就是不对了。

现在我们想一下长度为3的区间。经过我们的深思熟虑，可以得到可能是如下几种：

1. xy0
2. 0yx

这两种我们在进行补全都可以变成xyx的形式，然后在缩点缩成x的形式。

如果这样填完还会有空的点，不妨将剩下的位置填上这颗子树的root。

正确性的证明是从别的博客里面借鉴过来的(其实我这个构造方法也是那里学的，教练讲得有点潦草，我看了题解才懂得)

考虑这样做的正确性：
若不存在两个不为0的位置相邻，区间的首尾一定已经填入数字且相邻的两个已经填入数字的位置中恰好隔着一个0,此时将剩下的位置填成这棵子树的根显然正确；
若存在两个不为0的位置相邻，缩点之后不为0的位置减少了1,为0的位置也减少了1,两者的差不变，因此可以看做是递归下去，直到出现第1种情况。

特别的，我们对于\([1, 2n - 1]\) 要保证首尾相同，这样才是一个合法的序列。我们对这个进行一下分类讨论：

1. \(a_1, a_{2n-1} > 0\), \(a_1 ≠ a_{2n - 1}\) 非法序列
2. \(a_1, a_{2n - 1} > 0, a_1 = a_{2n - 1}\) 合法序列，直接递归就行了
3. 若\(a_1 > 0\) 或 \(a_{2n - 1} > 0\) 把另外一个填成和那个有的一样的就行了
4. 若\(a_1 = a_{2n - 1} = 0\),按照之前的那个算法，从左到右合并能够保证首尾相同并且没有剩余位0.

其实这个方法适用于所有的区间\([l, r]\)
然后我们用链表实现(数组模拟链表，不建议写指针)，复杂度\(O(n)\)

代码

这份代码是我之前写的 压行了 但是我觉得还是比较整洁的 应该还是可以看的

如果你觉得看起来不是很舒服 非常抱歉 自行换个行 谅解一下

# include <bits/stdc++.h>
using namespace std;

# define N 1000005
int n, m, now = 1, a[N], vis[N], nxt[N], pre[N], suf[N];

inline void Fail() { puts("no"), exit(0); }
inline int Get_ () { 
	while (vis[now]) ++now; 
	if (now > n) Fail(); 
	vis[now] = 1; return now; 
}
inline void del (int l, int r) { int tl = pre[l], tr = suf[r]; suf[tl] = tr, pre[tr] = tl; }

inline void Merge (int l, int r, int & x) {
	while (x > l && suf[suf[x]] && suf[suf[x]] <= r && !a[x] && a[suf[x]] && a[suf[suf[x]]]) 
		a[x] = a[suf[suf[x]]], del (suf[x], suf[suf[x]]), x = pre[pre[x]];
	while (x > l && suf[suf[x]] && suf[suf[x]] <= r && a[x] && a[suf[x]] && !a[suf[suf[x]]]) 
		a[suf[suf[x]]] = a[x], del (suf[x], suf[suf[x]]), x = pre[pre[x]];
}

inline void solve (int l, int r) {
# define rep for (int i = l ; i <= r; i = suf[i])
	if (r - l & 1) Fail(); 
	rep while(nxt[i]) { 
		if (nxt[i] > r) Fail(); solve(suf[i], pre[nxt[i]]); 
		del (suf[i], nxt[i]); nxt[i] = nxt[nxt[i]]; 
	}
	int num1 = 0, num2 = 0, rt = a[pre[l]]; rep num1 += a[i] > 0, ++num2;
	num2 = (num2 >> 1) + 1; if (num1 > num2) Fail(); num2 -= num1;
	for (int i = l; i <= r && num2; i = suf[i]) { if (!a[i]) a[i] = Get_ (), --num2; } 
	rep  Merge(l - 1, r, i); rep if (!a[i]) a[i] = rt;
}

signed main() {
	scanf ("%d", &n); if (n == 1) return puts("yes\n1"), 0; 
	m = (n << 1) - 1; for (int i = 1; i <= m; ++i) scanf ("%d", &a[i]); 
	for (int i = 2; i <= m; ++i) if (a[i] && a[i - 1] && a[i] == a[i - 1]) Fail();
	if (a[1] && a[m] && a[1] != a[m]) Fail(); a[1] = a[m] = a[1] | a[m]; 
	for (int i = 0; i <= m + 1; ++i) pre[i] = i - 1, suf[i] = i + 1; pre[0] = 0; 
	for (int i = m; i >= 1; --i) if (a[i]) nxt[i] = vis[a[i]], vis[a[i]] = i;
	solve(1, m), puts("yes"); for (int i = 1; i <= m; ++i) printf ("%d ", a[i]); return 0;
}