← 返回题目列表

AtCoder · agc010_c

C. 清洁

中文机器翻译题面 查看原题

分数: 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