409701: GYM103688 C Tree Division

You are given a tree of $$$n$$$ nodes, the i-th node has value $$$a_i$$$.

Define a node $$$t$$$ is valid, if you can divide the $$$n$$$ nodes into two sets $$$A$$$ and $$$B$$$, such that the following condition would hold:

• $$$\forall u,v\in A(u\neq v)$$$, if $$$u$$$ is on the path from $$$t$$$ to $$$v$$$, then $$$a_u<a_v$$$
• $$$\forall u,v\in B(u\neq v)$$$, if $$$u$$$ is on the path from $$$t$$$ to $$$v$$$, then $$$a_u>a_v$$$

You need to find out whether the node $$$1$$$ is valid.

The first line contains one integer $$$n(1\le n\le 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n(1\le a_i\le n)$$$.

The next $$$n−1$$$ lines each contains two integers $$$x$$$ and $$$y$$$ $$$(1\le x,y\le n)$$$, denoting an edge between node $$$x$$$ and $$$y$$$.

Output YES if node $$$1$$$ is valid, otherwise print NO.

8
8 1 4 2 5 6 3 7
3 7
5 3
2 4
5 2
6 5
8 6
1 8

YES

6
4 2 1 5 3 1
1 2
2 3
3 4
4 5
1 6

NO

In this case, node $$$1$$$ is valid.

A possible division is: $$$A=\{2,3\}$$$,$$$B=\{1,4,5,6,7,8\}$$$.