Maximizing Profit at JOI Power Plant

The JOI power plant has n base stations numbered from 1 to n. They are connected by n-1 bidirectional wires such that any station is reachable from any other station. Each base station may have at most one generator. Initially, all generator switches are turned off. As the plant manager, you may choose some generators to turn their switches to "on" (you are allowed to choose none).

The generators have the following property. Suppose base stations x, y, and z each have a generator. Moreover, suppose that there is a simple path (i.e. no wire is used twice) that passes through these three stations in the order x → y → z. If the generators at both stations x and z are turned on, then the generator at station y will be damaged.

A generator that is turned on and is not damaged will be activated. You earn 1 yen for every activated generator; however, you must pay 1 yen to repair every damaged generator (whether or not its switch was turned on). Your profit is the difference between your total earnings and your repair costs.

In addition to the wiring information, you are given the generator availability at each base station. If the i-th base station has a generator, then the i-th number in the input will be 1; otherwise it will be 0.

Your task is to choose which generators to turn on so as to maximize your profit. Formally, let G be the set of base stations that have a generator. You decide on a subset S ⊆ G whose switches are turned on. A generator at a base station v is damaged if there exist two distinct base stations x and z (which may or may not be in S) such that:

• Base stations x, y (=v), and z all have generators,
• There is a simple path in the tree that goes through x, v, z in that order, and
• The switches of the generators at both x and z are turned on.

The profit is calculated as follows:

[ \text{Profit} = \text{(# activated generators)} - \text{(# damaged generators)} ]

An activated generator is one whose switch is turned on and that is not damaged. Damaged generators incur a cost of 1 yen each. Note that a generator being damaged does not depend on whether its own switch is on.

Your goal is to maximize the profit.

Observation: In the tree of base stations, if you choose two base stations that are far apart, then every generator (whether or not its switch was turned on) that lies in between on the unique simple path will be damaged. Thus, careful selection is required. For example, choosing no generator yields a profit of 0; choosing a single generator yields a profit of 1; and choosing two adjacent generators (which have no base station between them) yields a profit of 2. In some cases (such as a star topology with many leaves) choosing several generators in a specific pattern may lead to even higher profit.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of base stations.

The second line contains n integers; the i-th integer is either 0 or 1. A 1 indicates that the i-th base station has a generator, and 0 indicates it does not.

Each of the next n−1 lines contains two integers A_i and B_i (1 ≤ A_i, B_i ≤ n), indicating that base stations A_i and B_i are connected by a wire.

outputFormat

Output a single integer, the maximum profit you can obtain.

sample

3
1 1 1
1 2
2 3

2