#P12921. [AGC010C] Cleaning

[AGC010C] Cleaning

题目描述

有一棵包含 NN 个顶点的树,顶点编号为 11 到 NN。此外,第 ii 条边连接顶点 aia_i 和顶点 bib_i,共 N−1N-1 条边。

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

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

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

输入格式

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

NN A1A_1 A2A_2 … ANA_N a1a_1 b1b_1 … aN−1a_{N-1} bN−1b_{N-1}

输出格式

如果可以移除所有石子,输出 YES;否则输出 NO。

输入输出样例 #1

输入 #1

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

输出 #1

YES

输入输出样例 #2

输入 #2

3
1 2 1
1 2
2 3

输出 #2

NO

输入输出样例 #3

输入 #3

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

输出 #3

YES

说明/提示

限制条件

  • 2≤N≤1052 \leq N \leq 10^5
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 0≤Ai≤1090 \leq A_i \leq 10^9
  • 给定的图一定是一棵树。

样例解释 1

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

  • 选择 44 和 55 作为叶子节点。此时,除 44 外的所有顶点各剩下 11 个石子。
  • 选择 11 和 55 作为叶子节点。此时,所有顶点上的石子都被移除。

由 ChatGPT 4.1 翻译