Lingering Regret

Uk-je regrets the problem he wrote, Valley Overflow, so he is imagining what his life will be like in the future as a poached chicken seller.

In a deep mountain valley of Nonsan Training Center, Uk-je lives after a gift wrapping factory went under in the Fourth Industrial Revolution. He sold poached chicken by the valley until he was drafted as a trainee.

Nonsan Valley has $N$ terraced valleys connected in a tree shape by $N - 1$ streams. Any two valleys are joined by exactly one path. Valley $i$ is at altitude $H_i$ meters. Valley 1 is the source, and every stream flows away from the source.

During shooting practice, Uk-je lost $N$ shell casings, one of which fell into each valley. He jumps to search for them and collect them.

When he jumps from a valley at altitude $H_a$ to a valley at altitude $H_b$ (where $H_a \ge H_b$), he bounces up $(H_a - H_b) / 2$ meters from $H_b$. He then rises to altitude $H_b + (H_a - H_b) / 2$ and can move to a valley $c$ with $H_c \le H_b + (H_a - H_b) / 2$. Then he bounces up again by $(H_b + (H_a - H_b) / 2 - H_c) / 2$ meters. Uk-je can only jump in the same direction as the streams. Jumps never change valley heights or stream directions.

$a \to b$ means Uk-je jumps from $a$ to $b$, where $a$ and $b$ stand for the altitudes of the two valleys. For $8 \to 2$, Uk-je bounces $(8 - 2) / 2 = 3$ meters and rises to altitude 5. He can then reach $8 \to 2 \to 5$ at most. $8 \to 2 \to 6$ and $8 \to 2 \to 7$ are impossible. For $8 \to 2 \to 2$, he jumps to altitude 5 via $8 \to 2$, falls into the valley at altitude 2, and bounces $(5 - 2) / 2 = 1.5$ meters, ending at altitude 3.5. In the example above, starting from 8 lets him reach every valley.

Uk-je does not even know which valley he is in. Assuming Uk-je starts in each valley, find how many shell casings he can recover. Uk-je can clone himself without limit, so each clone may take a different path to recover shells.

The first line contains the number of valleys $N$.

The second line contains the altitudes $H_1, H_2, \ldots, H_N$, separated by spaces.

Each of the next $N - 1$ lines contains the two valley numbers connected by one stream, separated by a space.

Print $N$ numbers on one line, separated by spaces. The $i$-th number is the count of shell casings Uk-je can recover if he starts in valley $i$.

$1 \le N \le 316,402$

$1 \le H_i \le 10^8$ ($1 \le i \le N$)

The $N - 1$ streams connect the valleys in a tree shape.