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.