Minimum Risk Dormitory Selection

A somewhat risky plan is about to be executed. The teacher, along with agents of van-e, periodically inspects dormitories. However, if a room is caught in a state of laziness (\(\text{tu\`i fei}\)) when being inspected, it results in a catastrophic "GG" state (i.e. the student is essentially out of the game). To resist the routine inspections, the \(oier\)s have formed an anti-inspection alliance. This alliance forms a tree with \(n\) nodes (dormitories) connected by \(n-1\) undirected edges, each having a weight of 1.

Each dormitory \(i\) is associated with a probability \(k_i\) representing the chance that its occupant is in a lazy state. The inspection works as follows: when the teacher inspects a room, there are two cases:

• If the room is in the studying state (i.e. not lazy), the teacher triggers an alarm. In the next time unit, all neighbouring rooms (i.e. those at distance 1) immediately cease being lazy (if they were lazy) and revert to studying.
• If the room is already in the lazy state, no alarm is triggered and the occupant is caught (GG).

However, note that \(sqn\) will only choose to be lazy in the rooms of ztz11, AK\(\grave{\rm y}\)e, and floatiy. Your task is to help determine in which one of these three candidate dormitories the probability of being caught while lazy is minimized.

The probability that a room \(i\) is caught can be described as follows. Assume that the initial state of each room is decided independently: room \(i\) is lazy with probability \(k_i\) and studying with probability \(1-k_i\). When the teacher inspects the rooms in a random order, if a candidate room \(i\) (where \(sqn\) might be lazy) is inspected before any of its neighbouring rooms that are initially studying, then if \(i\) was lazy it will be caught. In other words, the risk for candidate \(i\) is given by:

[ R(i)= k_i \cdot E\Bigl[\frac{1}{1+X}\Bigr], ]

where \(X\) is the number of neighbours of \(i\) (among its adjacent dormitories) that are in the studying state. Since each neighbour \(j\) is in the studying state with probability \(1-k_j\), we have \(X\) following a Poisson-binomial distribution. The expectation \(E\Bigl[\frac{1}{1+X}\Bigr]\) is taken over the randomness in the states of the neighbouring rooms.

You are given the tree and the probabilities \(k_i\) for each dormitory. Also, you are given the three candidate dormitories (by their indices) in which \(sqn\) might be lazy. Please compute the risk for each candidate and output the dormitory number with the minimum risk. In case of a tie, output the smallest dormitory number.

inputFormat

The input begins with an integer \(n\) representing the number of dormitories. The second line contains \(n\) space‐separated real numbers \(k_1, k_2, \ldots, k_n\), where \(k_i\) denotes the probability that dormitory \(i\) is in a lazy state. Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), representing an undirected edge between dormitories \(u\) and \(v\). The final line contains three distinct integers, corresponding to the dormitories of ztz11, AK\(\grave{\rm y}\)e, and floatiy, respectively.

outputFormat

Output a single integer: the dormitory number (1-indexed) among the three candidates at which the risk (i.e. the probability of being caught while lazy) is minimized. If there is a tie, output the smallest such dormitory number.

sample

5
0.5 0.6 0.7 0.8 0.9
1 2
1 3
3 4
3 5
2 3 5

3