Description

Mite (mi te) is a very mysterious substance on planet D, containing huge amounts of energy. On planet D, which uses mite as its main energy source, transporting and storing this mite energy has always been a major problem.

There are $N$ cities on planet D, numbered $1$ through $N$, with city $1$ being the capital. These $N$ cities are connected by $N-1$ one-way expressways, forming a directed tree rooted at city $1$ (the capital). The direction of each expressway is from a child to its parent. The tree is layered by depth: the root has depth $0$ and belongs to layer $1$; a child of the root has depth $1$ and belongs to layer $2$; and so on, a node of depth $i$ belongs to layer $i+1$.

After building the expressways, the D people began to consider how to store and transmit mite. Due to differing levels of development, each city has a different storage capacity. City $i$ has a mite storage unit with capacity $A_i$. Besides storing, a storage unit can also automatically collect mite from the atmosphere.

If, at 6 pm, some storage unit is not full, it will automatically collect mite from the atmosphere and will be filled before 6 am the next day; however, it is only safe to start this auto-collection when the storage unit is completely empty. Starting auto-collection when a storage unit is non-empty but not full may cause safety hazards.

Between 6 am and 7 am, the capital (city $1$) consumes all mite in its storage unit. The root does not auto-collect mite; it only accepts mite transmitted from its children.

At 7 am, cities start the transmission process, proceeding layer by layer: first, cities in layer $2$ transmit to layer $1$ (the root, city $1$), until the root’s storage is full or all layer-$2$ storage units are empty; then layer $3$ transmits to layer $2$, ensuring that for every node in layer $2$, its storage becomes full or all of its children’s (in layer $3$) storage units become empty; and so on, until the last layer completes transmission. The transmission process will certainly finish before 6 pm.

Due to technical reasons, the transportation plan must satisfy the following conditions:

1. No storage unit may remain non-empty but not full at 6 pm when transmission ends. Otherwise, it would start auto-collection while already containing mite, which is dangerous. In other words, by 6 pm, every storage unit must be either empty or full.
2. For the capital (city $1$), every day between 6 am and 7 am its storage unit is automatically emptied. The transportation plan does not need to consider how to move mite out of the capital.
3. Except for city $1$, each node must first send out all the mite originally stored in its own storage unit to its parent before its children transmit mite to it. Mixing locally stored mite with incoming mite is not allowed.
4. For any city, the amounts of mite sent to it from its multiple sources must be exactly the same. Otherwise, mixing different sources in different proportions may be dangerous.

Now that the expressways are built and each city has a storage unit with some capacity, to meet the above constraints, it may be necessary to rebuild some storage units. You may, and only may, destroy the existing storage unit in a city (including the capital) and build a new one with any positive capacity. The new capacity may be a real number (in the input, original capacities are positive integers, but rebuilt capacities may be fractional), and it cannot be negative or zero. Your goal is to minimize the number of storage units that need to be rebuilt.

Input Format

The first line contains a positive integer $N$, the number of cities.
The next $N$ lines each contain a positive integer; line $i$ gives the original capacity of the storage unit in city $i$.
Then follow $N-1$ lines, each containing two positive integers $a, b$, indicating there is a one-way expressway from city $b$ to city $a$ ($a \ne b$).

Output Format

Output a single line with one integer: the minimum number of storage units that must be rebuilt (i.e., whose capacities are modified).

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

3

Hint

Sample explanation: One optimal solution is to change $A_1$ to $8$, $A_3$ to $4$, and $A_5$ to $2$. Then the amounts sent from $2$ and $3$ to $1$ are equal, the amounts sent from $4$ and $5$ to $2$ are equal, and at 6 pm every day, $1$ and $2$ are full while $3$, $4$, and $5$ are empty, satisfying all constraints.

Constraints: For $100\%$ of the testdata, $N < 500000$, $A_j < 10^8$.

Translated by ChatGPT 5