题目描述

有一棵有 $N$ 个顶点的树，编号从 $1$ 到 $N$。其中第 $i$ 条边连接着顶点 $a_i$ 和 $b_i$。

当前，第 $i$ 个顶点上有 $A_i$ 个石头。确定是否可能通过重复执行以下操作来从所有顶点上移除所有的石头：

• 选择两个不同的叶子节点。然后，从连接这两个叶子节点的路径上的每个顶点上移除恰好一个石头。这里，叶子节点 是树中度数为 $1$ 的顶点，并且选择的叶子节点本身也被视为连接它们的路径上的顶点。

注意，如果路径上存在一个顶点上没有石头，则无法执行操作。

约束条件

• $2 ≤ N ≤ 10^5$
• $1 ≤ a_i,b_i ≤ N$
• $0 ≤ A_i ≤ 10^9$
• 给定的图是一棵树。

输入

从标准输入读取的输入数据格式如下：

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

输出

如果可以从所有顶点上移除所有石头，则打印 YES。否则，打印 NO。

示例 1

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

输出 1

YES

可以按照以下步骤移除所有的石头：

• 选择顶点 $4$ 和 $5$。然后，除了顶点 $4$ 外，每个顶点上都剩下了一个石头。
• 选择顶点 $1$ 和 $5$。然后，每个顶点上都没有石头。

示例 2

3
1 2 1
1 2
2 3

输出 2

NO

示例 3

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

输出 3

YES