Home

Contest: Task: Related: TaskB TaskD

Score : $700$ points

Problem Statement

There is a tree with $N$ vertices, numbered $1$ through $N$. The $i$-th of the $N-1$ edges connects vertices $a_i$ and $b_i$.

Currently, there are $A_i$ stones placed on vertex $i$. Determine whether it is possible to remove all the stones from the vertices by repeatedly performing the following operation:

  • Select a pair of different leaves. Then, remove exactly one stone from every vertex on the path between those two vertices. Here, a leaf is a vertex of the tree whose degree is $1$, and the selected leaves themselves are also considered as vertices on the path connecting them.

Note that the operation cannot be performed if there is a vertex with no stone on the path.

Constraints

  • $2 ≦ N ≦ 10^5$
  • $1 ≦ a_i,b_i ≦ N$
  • $0 ≦ A_i ≦ 10^9$
  • The given graph is a tree.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ … $A_N$
$a_1$ $b_1$
:
$a_{N-1}$ $b_{N-1}$

Output

If it is possible to remove all the stones from the vertices, print YES. Otherwise, print NO.

Sample Input 1

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

Sample Output 1

YES

All the stones can be removed, as follows:

  • Select vertices $4$ and $5$. Then, there is one stone remaining on each vertex except $4$.
  • Select vertices $1$ and $5$. Then, there is no stone on any vertex.

Sample Input 2

3
1 2 1
1 2
2 3

Sample Output 2

NO

Sample Input 3

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

Sample Output 3

YES