Astro Tree Verification

In this problem, you are given a tree with n nodes, where each node is assigned an integer value. A tree is called an Astro Tree if and only if for every node, the following condition holds:

$$ v(u) = \left(\sum_{w \in \text{descendants}(u)} v(w)\right) + \text{deg}(u)_{direct} $$

Here, \(v(u)\) is the value of node \(u\), \(\text{descendants}(u)\) represents all nodes in the subtree of \(u\) (i.e. all direct and indirect children), and \(\text{deg}(u)_{direct}\) is the number of direct children of \(u\). Note that for a leaf node, since there are no children, its value must be 0.

Your task is to determine whether the given tree is an Astro Tree.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of nodes in the tree.
• The second line contains n space-separated integers representing the values of the nodes. The i-th integer corresponds to the value of node i.
• The following n - 1 lines each contain two space-separated integers u and v, denoting an undirected edge connecting nodes u and v.

outputFormat

Output via standard output (stdout) a single line containing "YES" if the tree is an Astro Tree, or "NO" otherwise.

5
9 4 4 3 0
1 2
1 3
2 4
2 5

NO