Expected Beauty Walk

Vito lives in a city with n parks numbered from \(1\) to \(n\) connected by \(n-1\) roads such that any two parks are connected by a unique path (i.e. they form a tree). Each park \(i\) has a beauty value \(v_i\).

Last night Vito decided to take a walk in the city. His walking procedure is as follows. After visiting a park, he examines all roads adjacent to his current park. However, before setting out he observed from a skyscraper that every road has either a blue snake or a red snake. For a road connecting park \(i\) and park \(j\) with \(i<j\):

• A blue snake attacks anyone traveling from the smaller numbered park to the larger numbered park (i.e. moving from \(i\) to \(j\)).
• A red snake attacks anyone traveling from the larger numbered park to the smaller numbered park (i.e. moving from \(j\) to \(i\)).

To avoid snake attacks, when choosing a road to travel, Vito will only consider roads that are safe in the direction he is about to travel. Since each road is independently red or blue with equal probability, for any road connecting parks \(i\) and \(j\):

• If \(i<j\) then traveling from \(i\) to \(j\) is safe if and only if the snake is red (with probability \(\frac12\));
• If \(i>j\) then traveling from \(i\) to \(j\) is safe if and only if the snake is blue (with probability \(\frac12\)).

At a park with degree \(d\), the probability that a given adjacent road is safe in the outgoing direction is \(\frac12\). Thus, the total number of safe roads is a random variable; if there is at least one safe road, Vito will choose uniformly among them. Moreover, he dislikes stopping and will continue walking until he reaches a park where no adjacent road is safe.

Define the beauty of a route as the sum of the beauty values of all parks visited along that route (including the starting park). Given that each road’s snake color is chosen independently with probability \(\frac12\) for blue and red, Vito wonders: For each starting park \(i\), what is the expected beauty of his route?

Mathematical formulation. For \(i\) with degree \(d_i\), the probability that there is no safe road is \((\frac12)^{d_i}\) and the probability that there is at least one safe road is \(1 - (\frac12)^{d_i}\). When there is at least one safe road, the probability to move to any particular adjacent park is

[ \frac{1 - (\frac12)^{d_i}}{d_i}. ]

Thus the process obeys the recurrence

[ F(i) = v_i + \frac{1 - (\frac12)^{d_i}}{d_i}\sum_{j \in adj(i)} F(j), \quad \text{for } d_i \ge 1, ]

with the convention that if (d_i=0) (i.e. when (n=1)), then (F(i)=v_i). This system of linear equations has a unique solution which represents the expected beauty when starting from park (i).

inputFormat

The input is given as follows:

 n
 v1 v2 ... vn
 u1 v1
 u2 v2
 ...
 u_{n-1} v_{n-1}

Where:

• n is the number of parks (\(1 \le n \le ...\)).
• The second line contains \(n\) integers \(v_1, v_2, \ldots, v_n\) representing the beauty values of the parks.
• Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) indicating a road between parks \(u\) and \(v\).

outputFormat

Output a single line containing \(n\) numbers separated by spaces, where the \(i\)th number represents the expected route beauty when starting from park \(i\). Answers within an absolute or relative error of \(10^{-6}\) are accepted.

sample

2
1 2
1 2

2.666667 3.333333

</p>