Problem E
Gopher Residence

The Edmonton gopher population has expanded rapidly over the past few years. To accommodate this increased number of gophers, the city has built a vast gopher residence under the legislature building. The residence consists of $N$ rooms, the $i$th either has a unique room $p_ i$ above it, or is the exit room $i = 1$. When a gopher living in room $i$ exits the residence, the must travel up to room $p_ i$, and then to the room above $p_ i$ and so on, until they reach room $1$ and exit the residence.

Each room $i$ has $x_ i$ gophers who wish to live in the room. Each room also has a “travel capacity” $c_ i$, which upper bounds the number of gophers that may live under (and including) room $i$. All gophers leave the residence at exactly $9$ o’clock each morning, so if there are more than $c_ i$ gophers living under (and thus travelling through) room $i$, there will be a traffic jam.

You know that probably not all of the $x_ i$ gophers who say they wish to live in room $i$ will actually want to. In fact, each gopher will independently flip a coin and decide with probability $\frac{1}{2}$ whether they actually wish to live in the residence.

The problem is that after all gophers have determined if they actually want to live in the residence, it may not be possible to accommodate them all. That is, it may still be that for some rooms $i$ that there are more than $c_ i$ gophers that want to live in a room under (or including) room $i$. So the city will hold a lottery to determine which of these gophers actually get to live in the residence by repeating the following process: while some gopher that wants to live in the residence can be included without violating any capacities, pick one of them at random and add them to the residence.

The city is unsure of how many gophers will actually end up living in the residence and have asked you to calculate the expected number of gophers that will live there, subject to the above process.

Input

The first line of input contains one integer $N$, the number of rooms in the residence ($1 \leq n \leq 100$). The following $N - 1$ lines each contain two integers $u$ and $v$, indicating that $u$ is the room directly above $v$ ($1 \leq u < v \leq N$). It is guaranteed that every room except room $1$ has a room directly above it.

The final $N$ lines each contain two integers $x_ i, c_ i$, indicating that there are $x_ i$ gophers living in the $i$th room, and the capacity of the $i$th room is $c_ i$ ($0 \leq x_ i, c_ i \leq 100)$.

Output

Output the expected number of gophers living in the residence as a real number. Your answer will be considered correct as long as the relative or absolute error is at most $10^{-6}$.

1
5 3

2.28125000000000000000

4
1 2
2 3
3 4
2 1
2 1
1 1
1 1

0.98437500000000000000

4
1 2
2 3
2 4
0 5
0 4
5 3
5 3

3.75000000000000000000