Meat is a very mysterious substance on planet D that contains enormous energy. On planet D, where meat is the primary energy source, the transportation and storage of this energy have always been a major problem.

There are $N$ cities on planet D, which we label from $1$ to $N$, with city $1$ being the capital. These $N$ cities are connected by $N-1$ one-way high-speed channels, forming a tree rooted at city $1$ (the capital). The direction of the high-speed channels is from the child node to the parent node in the tree. The tree is layered by depth: the root node has a depth of $0$ and belongs to layer $1$; the children of the root node have a depth of $1$ and belong to layer $2$; and so on, where nodes at depth $i$ belong to layer $i+1$.

After the high-speed channels are built, the inhabitants of planet D began to consider how to specifically store and transport meat resources. Due to different levels of development, each city's ability to store meat varies. Specifically, the $i$-th city has a meat storage unit with a capacity of $A[i]$. In addition to storage, this unit has the ability to automatically collect meat. If a storage unit is not full by 6:00 PM, it will automatically collect meat energy from the atmosphere and be full by 6:00 AM the next morning. However, it is only safe to start the automatic collection program when the storage unit is completely empty; starting it when the unit is neither full nor empty may pose safety risks. Between 6:00 AM and 7:00 AM, the root node city (city $1$) will consume all the meat in its storage unit. The root node does not automatically collect meat; it only receives meat transported from its child nodes. At 7:00 AM, the meat transportation process between cities begins, proceeding layer by layer: first, nodes in layer $2$ transport to layer $1$ (the root node, city $1$) until the storage unit of layer $1$ is full or the storage units of layer $2$ are all empty; then, layer $3$ transports to layer $2$, and so on, until the last layer is finished. The transportation process is guaranteed to be completed before 6:00 PM.

Due to technical reasons, the transportation plan must satisfy the following conditions: 1. No storage unit can be in a state that is neither empty nor full at 6:00 PM when transportation ends, as the unit would still trigger the automatic collection program, which could be dangerous if the unit already contains meat. In other words, every storage unit must be either empty or full at 6:00 PM. 2. Regarding the capital (city $1$), since the meat in its storage unit is automatically consumed between 6:00 AM and 7:00 AM every day, the transportation plan does not need to consider how to transport meat out of the capital. 3. Except for city $1$, every node must transport all the meat originally stored in its unit to its parent node before its child nodes transport meat to it. It is not allowed for residual meat in the storage unit to mix with incoming meat. 4. The amount of meat transported to a city from its various sources must be exactly the same; otherwise, mixing meat from different sources in different proportions may cause danger.

Now, the inhabitants of planet D have already built the high-speed channels, and each city has a storage unit with a certain capacity. To satisfy the above constraints, it may be necessary to rebuild the meat storage units in some cities. You can, and only can, destroy the existing meat storage unit in a city (including the capital) and build a new one with any capacity. The capacity can be a decimal (the original capacities in the input are positive integers, but the new capacities can be decimals), but it cannot be negative or zero. The goal is to minimize the number of storage units that need to be rebuilt.

Input

The input file is named meat.in. The first line contains a positive integer $N$, representing the number of cities. The next $N$ lines each contain a positive integer, where the $i$-th line represents the original capacity of the meat storage unit in city $i$. The next $N-1$ lines each contain two positive integers $a, b$, representing a high-speed channel from city $b$ to city $a$ ($a \neq b$).

Output

The output file is named meat.out. The output contains only one line, an integer, representing the minimum number of storage units that need to be rebuilt (i.e., modified).

Examples

Input 1

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

Output 1

3

Note

An optimal solution is to change $A[1]$ to $8$, $A[3]$ to $4$, and $A[5]$ to $2$. In this way, the amounts transported from $2$ and $3$ to $1$ are equal, and the amounts transported from $4$ and $5$ to $2$ are equal. At 6:00 PM, $1$ and $2$ are full, while $3, 4,$ and $5$ are empty, satisfying all constraints.

Constraints

For $20\%$ of the data, $N \le 20$; For $50\%$ of the data, $N \le 2000$; For $100\%$ of the data, $N \le 500000, A[i] \le 10^8$.

Figure 1. Tree structure of cities on planet D