配点 : $700$ 点

問題文

$N$ 頂点からなる木があり、頂点には $1$ から $N$ の番号がついています。 また、$N-1$ 本の辺の内、$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

今、各頂点 $i$ には $A_i$ 個の石が置いてあります。 以下の操作を繰り返して、全ての石を取り除くことができるか判定してください。

• 相異なる $2$ つの葉を一組選ぶ。そして、その $2$ 頂点間のパス上にある頂点全てからちょうど $1$ つ石を取り除く。 ただし、葉とは木の頂点で次数が $1$ の頂点を指し、選んだ葉自体もパス上の頂点として考える。

石が置かれていない頂点がパス上にあるときは、その操作を行えないことに注意してください。

制約

• $2 \leq N \leq 10^5$
• $1 \leq a_i,b_i \leq N$
• $0 \leq A_i \leq 10^9$
• 与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ … $A_N$

$a_1$ $b_1$

:

$a_{N-1}$ $b_{N-1}$

出力

全ての石を取り除くことができるなら YES を、そうでないなら NO を出力せよ。

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

YES

以下のようにすれば、すべての石を取り除くことができます。

• 葉として $4$ と $5$ を選ぶ。このとき、$4$ 以外の頂点に石が $1$ 個残る。
• 葉として $1$ と $5$ を選ぶ。このとき、全ての頂点から石がなくなる。

3
1 2 1
1 2
2 3

NO

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

YES