CF1508E Tree Calendar

小糸侑和七海燈子新婚啦！在婚礼当天，侑送给燈子一棵有 $n$ 个结点、以 $1$ 号结点为根的有向树，以及一个标号 $a$，它是该树的某种 DFS 序。树中的每条边都从根节点指向子节点。 调用 dfs(1) 后，以下算法会返回以 $1$ 为根的树的一个 DFS 序 $a$： ``` order := 0 a := array of length n function dfs(u): order := order + 1 a[u] := order for all v such that there is a directed edge (u -> v): dfs(v) ``` 注意，对于给定的树，可能存在不同的 DFS 序。 燈子非常喜欢这个礼物，于是决定玩一玩！在婚礼后的每一天，燈子都会执行以下操作一次： - 在所有满足 $a_u < a_v$ 的有向边 $u \rightarrow v$ 中，选择字典序最小的 $(a_{u'}, a_{v'})$ 对应的边 $u' \rightarrow v'$。 - 交换 $a_{u'}$ 和 $a_{v'}$。 距离婚礼已经过去了好几天，燈子已经忘记了婚礼是哪一天，也忘记了最初的标号 $a$！担心侑会生气，燈子决定请你帮忙推断出这两个信息。 作为她的好朋友，你需要根据当前的标号，求出距离婚礼已经过去了多少天，以及树的最初标号。如果当前标号无法通过上述过程从某个初始标号得到，请告知燈子。

第一行包含一个整数 $n$（$2 \le n \le 3 \cdot 10^5$），表示树的结点数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$，且所有 $a_i$ 互不相同），表示当前的标号。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u, v \le n$，$u \ne v$），表示一条从 $u_i$ 指向 $v_i$ 的有向边。所有边构成一棵以 $1$ 为根的有向树。

如果当前标号无法通过上述过程从某个 DFS 序得到，输出 NO。 否则，第一行输出 YES。第二行输出一个整数，表示距离婚礼已经过去了多少天。第三行输出 $n$ 个用空格分隔的整数，表示树的最初标号。 如果有多组正确答案，可以输出任意一组。也就是说，你可以输出任意一组（DFS 序，天数），使得从你给出的 DFS 序经过恰好该天数的操作后能得到当前的标号。

下图展示了第一个样例测试的动画。节点内的白色数字表示节点编号 $i$，橙色方框内的数字表示 $a_i$ 的值。  由 ChatGPT 4.1 翻译