CF1508E 题解

First Post:

Last Update:

非常好题目。做完之后感觉，自己归纳性质的能力需要加强，不能让思考仅仅停留在手玩和感性理解，要尝试将一些东西往已知的模型上想。

设 在树原来的 dfs 序为位置 。

手玩一下操作过程，发现操作可以分为若干个阶段，每个阶段都是将数 从根换到下面，并把 换到根。

换 的时候，它会沿着 最小的一条链一路换下去，最后换到某个叶子。事实上，这个叶子就是 DFS 过程中，第一个出栈的节点。

换完之后，除这个叶子，剩下的 个节点上的数仍然按原来的 DFS 序排列，也就是说，这个过程可以归纳地进行下去。

那我们就知道树上的数在很多次操作后的形状了。每个节点上的数将从 DFS 序变为出栈序。

而且，每次将数 恰好换到其对应位置的时候，数 所在的节点的出栈序是 ，而数 在剩下的节点中，按 DFS 序的顺序排列。

再次观察操作过程，发现任何时候，儿子之间 的相对大小关系是不变的。

证明：

考虑点 和它的儿子 ，。

一次关于 的交换， 显然会找到第一个 的儿子 。所以有 。

那么将 替换为 ，相对大小关系肯定不变。

而如果还要交换 与其子节点，显然 仍然成立，同时， 不是这个操作阶段正在下移的数的目标节点。

所以，在交换之后， 的值，在 这个操作阶段结束前，值都不会改变，所以它们仍然按原图的 DFS 序排列，所以它们的相对大小关系不变。

那么 就直接可以通过将 排序后 DFS 来产生，所以题面中的“多解输出任意解”是假的。

回到原问题。

考虑先算出当前在哪个操作阶段。如果 ，说明此时未进行任何操作，否则当前阶段数就是 。（即数 正在从上往下移动）。令 。

算出来之后，手动回退一部分操作，使得当前局面为该阶段的开头。

接下来检查合法性，我们需要确保 都换到了出栈序为 的节点，同时 按原来的 DFS 序排列。

然后计算天数。 中的每个节点，都是从根换到其现在的位置的，所以答案就是之前回退的天数加上 ，其中 表示数 现在的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n;
int a[N];
int fir[N],nxt[N << 1],to[N << 1],ect = 1;
inline void addedge(int u1,int v1) {
	nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;
}
vector<int> sons[N];
int dep[N],fa[N];
int pos[N];
int frt[N]; // 最初的 dfs 序
int ext[N]; // 出栈序
long long ans;
void dfs0(int x,int f) 
{
	for(int i = fir[x],y;y = to[i],i;i = nxt[i]) {
		if(y == f) continue;
		dep[y] = dep[x] + 1;
		fa[y] = x;
		dfs0(y,x);
		sons[x].push_back(y);
	}
	sort(sons[x].begin(),sons[x].end(),[&](const int &x,const int &y) { return a[x] < a[y];});
}
int ps_frt[N],ps_ext[N];
void dfs1(int x) {
	frt[x] = ++frt[0];ps_frt[frt[x]] = x;
	for(auto y : sons[x]) dfs1(y);
	ext[x] = ++ext[0];ps_ext[ext[x]] = x;
}
bool Isanc(int u,int v) { // v 是不是 u 的祖先
	if(u == v) return true;
	if(u == 1) return false;
	return Isanc(fa[u],v);
}
void GoBack(int u) {
	if(u == 1) return;
	swap(a[u],a[fa[u]]);
	++ans;
	GoBack(fa[u]);
} 
int main() {
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1,u,v;i < n;i++)
		cin >> u >> v,addedge(u,v),addedge(v,u);
	dfs0(1,0);
	dfs1(1);
	if(a[1] == 1) {
		for(int i = 1;i <= n;i++)
			if(frt[i] != a[i]) return puts("NO"),0;
		puts("YES");
		puts("0");
		for(int i = 1;i <= n;i++) printf("%d ",frt[i]);printf("\n");
		return 0;
	}
	int cur = a[1] - 1; // 当前调整到的值	
	for(int i = 1;i <= n;i++) pos[a[i]] = i;
	if(!Isanc(ps_ext[cur],pos[cur])) return puts("NO"),0; // 无法调整到出栈序位置
	GoBack(pos[cur]);
	for(int i = 1;i <= n;i++) pos[a[i]] = i;
	for(int i = 1;i < cur;i++)
		if(ext[pos[i]] != i) return puts("NO"),0;
	for(int i = cur;i < n;i++)
		if(frt[pos[i]] > frt[pos[i + 1]]) return puts("NO"),0;
	puts("YES");
	for(int i = 1;i < cur;i++) ans += dep[pos[i]];
	printf("%lld\n",ans);
	for(int i = 1;i <= n;i++) printf("%d ",frt[i]);printf("\n");
	return 0;
}
≡