Tree Calendar
Contest: Codeforces Round 715 (Div. 1)
Difficulty rating: 3100
Tags: brute force, constructive algorithms, data structures, dfs and similar, sortings, trees

Yuu Koito and Touko Nanami are newlyweds! On the wedding day, Yuu gifted Touko a directed tree with $$$n$$$ nodes and rooted at $$$1$$$, and a labeling $$$a$$$ which is some DFS order of the tree. Every edge in this tree is directed away from the root.

After calling dfs(1) the following algorithm returns $$$a$$$ as a DFS order of a tree rooted at $$$1$$$ :

Note that there may be different DFS orders for a given tree.

Touko likes the present so much she decided to play with it! On each day following the wedding day, Touko performs this procedure once:

- Among all directed edges $$$u \rightarrow v$$$ such that $$$a_u < a_v$$$, select the edge $$$u' \rightarrow v'$$$ with the lexicographically smallest pair $$$(a_{u'}, a_{v'})$$$.
- Swap $$$a_{u'}$$$ and $$$a_{v'}$$$.

Days have passed since their wedding, and Touko has somehow forgotten which date the wedding was and what was the original labeling $$$a$$$! Fearing that Yuu might get angry, Touko decided to ask you to derive these two pieces of information using the current labeling.

Being her good friend, you need to find the number of days that have passed since the wedding, and the original labeling of the tree. However, there is a chance that Touko might have messed up her procedures, which result in the current labeling being impossible to obtain from some original labeling; in that case, please inform Touko as well.

Input format:
The first line of the input contains an integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of nodes on the tree.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le n$$$, all $$$a_i$$$ are distinct) — the current labeling of the tree.

Each of the next $$$n - 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), describing an directed edge from $$$u_i$$$ to $$$v_i$$$. The edges form a directed tree rooted at $$$1$$$.

Output format:
If the current labeling is impossible to arrive at from any DFS order, print NO.

Else, on the first line, print YES. On the second line, print a single integer denoting the number of days since the wedding. On the third line, print $$$n$$$ numbers space-separated denoting the original labeling of the tree.

If there are multiple correct outputs, print any. This means: you are allowed to output any pair (DFS order, number of days), such that we get the current configuration from the DFS order you provided in exactly the number of days you provided.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
The following animation showcases the first sample test case. The white label inside the node represents the index of the node $$$i$$$, while the boxed orange label represents the value $$$a_i$$$.

Example input:
7
4 5 2 1 7 6 3
1 5
7 6
1 2
2 7
3 4
1 3

Example output:
YES
5
1 4 2 3 7 6 5

Example input:
7
7 6 5 3 1 4 2
4 3
2 5
3 7
1 4
7 2
2 6

Example output:
NO

Editorial:
From the structure, we see that until the end, the process is divided into $$$n$$$ phases, where the $$$i$$$-th involves phase pushing value $$$i$$$ from the root to the smallest-labeled leaf. Also in the following tutorial, I will use post-order and exit order, as well as pre-order and DFS order interchangeably.
Lemma 1. After finishing pushing $$$i$$$, labels $$$1$$$ to $$$i$$$ are at the post-order positions, and the remaining labels from $$$i + 1$$$ to $$$n$$$ form the pre-order of the remaining part of the tree offsetted by $$$i$$$.
Proof. There's a formal proof, but I think a better way is to show an illustration instead.
After pushing $$$i$$$, we see that all green labels (label from $$$1$$$ to $$$i$$$) are at their post-order positions, while all red labels (labels from $$$i + 1$$$ to $$$n$$$) are connected and form the pre-order of the red subtree, with an offset of $$$i$$$. Moreover, this suggests that while pushing $$$i$$$, the label of the root is $$$i + 1$$$.
Lemma 2. On any day, the order of the values of the children of any node stays the same.
The proof will be left as an exercise for the reader, but a hint would be that for any node, a prefix of its children will be green nodes (nodes that have been pushed), the rest are red nodes (nodes that haven't been pushed). We can prove that the green nodes are ordered the same, the red nodes are ordered the same, and the green nodes are always less than the red nodes.
Lemma 3. Suppose we are pushing/have just finished pushing $$$i$$$. Then the number of days that have passed is the sum of heights of all labels from $$$1$$$ to $$$i$$$.
Proof. All labels that have finished being pushed, or are being pushed, have all traversed from the root down to their current position, which means the number of days to push each of these labels is equal to the height of the node containing the label.
With the three lemmas, we can finally discuss the algorithm: First, we sort the children of each node by its value. Then we use this order to create the pre-order of the tree, and we can also figure out the current value that is being pushed (it is the value of the root minus 1). Call this value $$$v$$$. Knowing the current value being pushed, we first check if the current value is being pushed to the correct destination (i.e. check if the node with label $$$v$$$ is an ancestor of the node with post-order $$$v$$$). Then, we can "revert" the pushing of $$$v$$$ by swapping it back up the root, also taking to account the number of days. Finally, we check if values $$$< v$$$ are in the post-order positions, and values that are $$$\ge v$$$ form the pre-order shifted by $$$v - 1$$$ of the remaining of the tree.
Complexity is $$$O(n \log n)$$$.