Water Temperature Reduction on a Rooted Tree

We are given a rooted tree with (n) nodes (numbered from 1 to (n)) with root (1). Each node (i) has a cup of water with initial temperature (a_i). Small S wishes to make the temperature of every cup equal to zero. However, she may only perform two kinds of operations any number of times (possibly zero):

• Heating operation: Choose any node \(i\) and activate its heating device. This increases the temperature of every cup in the subtree rooted at \(i\) (including \(i\) itself) by \(1\);
• Wind operation: Choose any leaf node \(i\) and blow wind from that node toward the root. This decreases the temperature of every cup on the unique path from \(i\) to the root by \(1\).

The task is to decide whether it is possible to make the temperature of every cup become exactly zero by a sequence of these operations.

Important observations:
Since heating operations on a node affect the entire subtree and wind operations (which can only start at a leaf) affect the whole path from that leaf to the root, most operations add/subtract the same amount on many nodes. In fact, if we denote by \(x_i\) the total number of heating operations performed at node \(i\) (for \(1 \le i \le n\)) and by \(y_i\) (for a leaf \(i\)) the number of wind operations starting at \(i\), then the final temperature at a node \(v\) is \[ a_v + \sum_{u\in \text{anc}(v)} x_u - \sum_{\substack{\ell\;\text{is a leaf}\\ v\in \text{path}(\ell)}} y_\ell = 0. \] A key invariant is that a heating operation at a non‐root node can be used to adjust the difference between a node and its parent – note that the wind operation subtracts the same value from every cup on the path, so it does not change the difference. In particular, if we try to equalize the temperatures along the edge from a parent \(p\) to its child \(c\) (before applying wind operations to finally bring them down to 0), then we must use heating at \(c\) to raise \(a_c\) to \(a_p\); that is, we would need \[ x_c = a_p - a_c \quad (\text{which requires }a_p \ge a_c). \] Once every child is raised to its parent’s temperature, every node along any path from the root will have the same temperature as \(a_1\).

After such equalization, a wind operation starting at the unique leaf on that path decreases the temperature of every cup along that path by \(1). Therefore, if the tree has exactly one leaf (i.e. the tree is a chain) then we can make every cup zero provided that for every edge from a parent \(p\) to a child \(c\) we have \(a_p\ge a_c\).

On the other hand, if the tree has more than one leaf then note that a wind operation may be initiated at each leaf. The catch is that any internal node (which lies in the paths from several leaves) will receive the sum of wind effects from all leaves in its subtree. In order for the internal node’s temperature to become zero, we must have \[ a_1 - \Bigl(\sum_{\ell\;\in \;\text{leaves}} y_\ell\Bigr) = 0. \] Since equalization forces every node to have temperature equal to \(a_1\) before wind operations, each leaf must contribute exactly \(a_1\) wind operations along its unique path. This causes the root to be subtracted by \(\text{(number of leaves)}\times a_1\). Thus, if the tree has more than one leaf, it is necessary (and indeed sufficient) that

(1) For every edge from a parent \(p\) to its child \(c\), it holds that \(a_p \ge a_c\) (so we can raise \(a_c\) up to \(a_p\) using heating), and
(2) The tree has exactly one leaf or \(a_1 = 0\).

In summary, the answer is "YES" if and only if for every non-root node \(c\) with parent \(p\) we have \(a_p \ge a_c\), and additionally, if the tree has more than one leaf then we must have \(a_1 = 0\). Otherwise, the answer is "NO".

Note: In a tree that is a single node (\(n=1\)), the only node is considered a leaf and the answer is always "YES".

inputFormat

The input begins with a line containing a single integer (n) ((1 \le n \le 10^5)), the number of nodes in the tree. The next line contains (n) integers (a_1, a_2, \ldots, a_n) ((|a_i| \le 10^9)) representing the initial temperatures. Each of the following (n-1) lines contains two integers (u) and (v) ((1 \le u, v \le n)) describing an edge of the tree. The tree is rooted at node (1).

outputFormat

Output a single line containing either “YES” if it is possible to make every cup’s temperature equal to 0 using the operations, or “NO” otherwise.

sample

1
5

YES