Codeforces1508D - Tree Calendar

Posted on Edited on In

Codeforces1508D - Tree Calendar

题目大意：

有一棵已知的有根树和一个未知的 \(\text{dfs}\) 序，且做了若干次操作，每次操作是

对于所有的 \((u,fa_u)\and label_{fa_u}<label_{u}\) ，找到最小的二元组 \((label_{fa_u},lable_u)\) ，交换二元组的 \(label\)

给定最终的序列，求复原一个 \(\text{dfs}\) 序并且给出操作次数，或者确定不存在这样的 \(\text{dfs}\) 序

\[ \ \]

模拟这样的过程，容易发现：

1号节点沿着最小 \(\text{dfs}\) 序路径走下去，直到叶子，同时将路径上的点推上来，一共推了 \(dep_{leaf}\) 次

2号节点沿着最小 \(\text{dfs}\) 序路径走下去，直到叶子，同时将路径上的点推上来，一共推了 \(dep_{leaf'}\) 次

....

考虑每个节点都已经推到最底下的情况，则最终所有的节点有两种情况

1.是推下来的节点，则其 \(label\) 恰好为原树上出栈序列的标号

2.剩下的点构成一个新的连通块，按照新的 \(\text{dfs}\) 序的顺序标号

那么考虑找到当前最小的二元组 \((label_{fa_u},label_u)\) ，就知道当前正在推的是哪个元素

考虑先复原这个元素被推下来的过程，复原的过程中注意判定是否当前的元组合法

然后容易通过当前的 \(label\) 确定一开始的 \(\text{dfs}\) 序

具体的，设 \(s_u\) 为 \(u\) 子树中最小的 \(label\) ，按照 \(s_u\) 递增的顺序遍历每个儿子得到的 \(\text{dfs}\) 才可能是合法的 \(\text{dfs}\) 序

原理比较显然，已经被推的叶子按照 \(\text{stack}\) 序遍历，剩下的按照原先的 \(\text{dfs}\) 序遍历，最终取 \(\text{min}\) 然后遍历即合法

然后按照上面的过程，对于得到的 \(\text{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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=3e5+10;

int n;
int A[N],F[N];
vector <int> G[N];
ll ans;
int X[N],Y[N],Z[N],C1,C2,C3,D[N];
// X 原树 dfs 序
// y 原树 stack 序
// z 删去已经推完的点之后，剩下的点的 dfs 序

int I[N],J[N];
void dfs1(int u){
	I[u]=A[u];
	for(int v:G[u]) D[v]=D[u]+1,dfs1(v),cmin(I[u],I[v]);
}
void dfs2(int u){
	J[X[u]=++C1]=u;
	sort(G[u].begin(),G[u].end(),[&](int x,int y){ return I[x]<I[y]; });
	for(int v:G[u]) dfs2(v);
	Y[u]=++C2;
}
int vis[N];
void dfs3(int u){
	if(vis[u]) return;
	Z[u]=++C3;
	for(int v:G[u]) dfs3(v);
}

int main(){
	n=rd();
	rep(i,1,n) A[i]=rd();
	int p=n+1; A[n+1]=n+1;
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),F[v]=u;
		if(A[u]<A[v] && A[p]>A[u]) p=u;
	}
	int f=1;
	if(p<=n) while(F[p]) {
		int f=F[p];
		// illgal swap
		if(A[f]<A[p]) return puts("NO"),0;
		swap(A[p],A[F[p]]);
		
		// not optimal swap
		if(F[f] && A[F[f]]<A[f]) return puts("NO"),0;
		for(int v:G[f]) if(A[v]>A[f] && A[v]<A[p]) return puts("NO"),0;
		p=F[p],ans++;
	}
	dfs1(1),dfs2(1);
	rep(i,1,n) if(A[i]<A[p]) f&=A[i]==Y[i],vis[i]=1,ans+=D[i];
	dfs3(1);
	rep(i,1,n) if(A[i]>=A[p]) f&=Z[i]+A[p]-1==A[i];
	if(!f) puts("NO");
	else {
		puts("YES");
		printf("%lld\n",ans);
		rep(i,1,n) printf("%d ",X[i]);
		puts("");
	}
}