分数: 700 点
问题陈述
有一棵树 N 顶点,编号 1 通过 N。 的 i- 第 N-1 边连接顶点 a_i 和 b_i.
目前,有 A_i 石头放置在顶点 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