Score : 700 points
There is a tree with N vertices, numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.
Currently, there are A_i stones placed on vertex i. Determine whether it is possible to remove all the stones from the vertices by repeatedly performing the following operation:
Note that the operation cannot be performed if there is a vertex with no stone on the path.
The input is given from Standard Input in the following format:
N A_1 A_2 … A_N a_1 b_1 : a_{N-1} b_{N-1}
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:
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