Expected Charged Components in SHOI Probabilistic Charger

SHOI has released its new probabilistic charger. The charger consists of \(n\) charging components connected by \(n-1\) wires. When powering on the charger, each wire becomes conductive with probability \(p\) and each charging component is directly charged with probability \(q\), independently. Once a component is directly charged, the electric energy can flow through any conductive wire, and all components in the same connected group (formed by conductive wires) will eventually be charged.

For a given wire configuration, if a connected component has \(s\) nodes then the probability that none of them gets directly charged is \((1-q)^s\) and thus the probability that the component gets charged is \(1-(1-q)^s\). In such a case, all \(s\) nodes will be charged. Therefore, the expected number of charged components in that configuration is \(\sum (s\cdot (1-(1-q)^s))\), where the sum is over all connected components in the random subgraph induced by conductive wires.

Your task is to compute the overall expectation over all configurations of wires. It is guaranteed that the \(n\) components are connected by \(n-1\) wires (forming a tree). The randomness comes first from the state of the wires and then from the direct charging of each component.

The answer should be output as a real number.

inputFormat

The input consists of:

• The first line contains an integer \(n\) representing the number of charging components.
• The second line contains two real numbers \(p\) and \(q\): the probability that a wire is conductive and the probability that a component is directly charged, respectively.
• Then \(n-1\) lines follow, each containing two integers \(u\) and \(v\), which denote that there is a wire connecting component \(u\) and component \(v\). The components are numbered from 1 to \(n\).

outputFormat

Output a single real number, representing the expected number of charged components.

sample

1
0.5 0.5

0.5