题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。此外，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$，共 $N-1$ 条边。

现在，每个顶点 $i$ 上放有 $A_i$ 个石子。请判断是否可以通过重复以下操作，将所有石子全部移除。

• 选择两个不同的叶子节点作为一组。然后，从这两个顶点之间的路径上的所有顶点（包括这两个叶子节点本身）各取走恰好 $1$ 个石子。 这里，叶子节点指的是度数为 $1$ 的顶点，且所选叶子节点也算作路径上的顶点。

注意，如果路径上的某个顶点没有石子，则无法进行该操作。

输入格式

输入以如下格式从标准输入读入。

$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

输出

YES

样例 2

输入

3
1 2 1
1 2
2 3

输出

NO

样例 3

输入

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

输出

YES

说明/提示

限制条件

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

样例解释 1

可以按如下方式移除所有石子：

• 选择 $4$ 和 $5$ 作为叶子节点。此时，除 $4$ 外的所有顶点各剩下 $1$ 个石子。
• 选择 $1$ 和 $5$ 作为叶子节点。此时，所有顶点上的石子都被移除。

由 ChatGPT 4.1 翻译