atcoder#AGC010C. [AGC010C] Cleaning

[AGC010C] Cleaning

Score : 700700 points

Problem Statement

There is a tree with NN vertices, numbered 11 through NN. The ii-th of the N1N-1 edges connects vertices aia_i and bib_i.

Currently, there are AiA_i stones placed on vertex ii. Determine whether it is possible to remove all the stones from the vertices by repeatedly performing the following operation:

  • Select a pair of different leaves. Then, remove exactly one stone from every vertex on the path between those two vertices. Here, a leaf is a vertex of the tree whose degree is 11, and the selected leaves themselves are also considered as vertices on the path connecting them.

Note that the operation cannot be performed if there is a vertex with no stone on the path.

Constraints

  • 2N1052 \leq N \leq 10^5
  • 1ai,biN1 \leq a_i,b_i \leq N
  • 0Ai1090 \leq A_i \leq 10^9
  • The given graph is a tree.

Input

The input is given from Standard Input in the following format:

NN

A1A_1 A2A_2ANA_N

a1a_1 b1b_1

:

aN1a_{N-1} bN1b_{N-1}

Output

If it is possible to remove all the stones from the vertices, print YES. Otherwise, print NO.

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

All the stones can be removed, as follows:

  • Select vertices 44 and 55. Then, there is one stone remaining on each vertex except 44.
  • Select vertices 11 and 55. Then, there is no stone on any vertex.
3
1 2 1
1 2
2 3
NO
6
3 2 2 2 2 2
1 2
2 3
1 4
1 5
4 6
YES