Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Maze

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA maze is represented by a tree (an undirected graph, where exactly one way exists between each pair of vertices). In the maze the entrance vertex and the exit vertex are chosen with some probability. The exit from the maze is sought by Deep First Search. If there are several possible ways to move, the move is chosen equiprobably. Consider the following pseudo-code:

DFS(x)

if x == exit vertex then

finish search

flag[x] <- TRUE

random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen

for i <- 1 to length[V] do

if flag[V[i]] = FALSE then

count++;

DFS(y);

count++;

*V*(*x*) is the list vertices adjacent to *x*. The *flag* array is initially filled as FALSE. *DFS* initially starts with a parameter of an entrance vertex. When the search is finished, variable *count* will contain the number of moves.

Your task is to count the mathematical expectation of the number of moves one has to do to exit the maze.

Input

The first line determines the number of vertices in the graph *n* (1 ≤ *n* ≤ 10^{5}). The next *n* - 1 lines contain pairs of integers *a*_{i} and *b*_{i}, which show the existence of an edge between *a*_{i} and *b*_{i} vertices (1 ≤ *a*_{i}, *b*_{i} ≤ *n*). It is guaranteed that the given graph is a tree.

Next *n* lines contain pairs of non-negative numbers *x*_{i} and *y*_{i}, which represent the probability of choosing the *i*-th vertex as an entrance and exit correspondingly. The probabilities to choose vertex *i* as an entrance and an exit equal and correspondingly. The sum of all *x*_{i} and the sum of all *y*_{i} are positive and do not exceed 10^{6}.

Output

Print the expectation of the number of moves. The absolute or relative error should not exceed 10^{ - 9}.

Examples

Input

2

1 2

0 1

1 0

Output

1.00000000000000000000

Input

3

1 2

1 3

1 0

0 2

0 3

Output

2.00000000000000000000

Input

7

1 2

1 3

2 4

2 5

3 6

3 7

1 1

1 1

1 1

1 1

1 1

1 1

1 1

Output

4.04081632653

Note

In the first sample the entrance vertex is always 1 and the exit vertex is always 2.

In the second sample the entrance vertex is always 1 and the exit vertex with the probability of 2/5 will be 2 of with the probability if 3/5 will be 3. The mathematical expectations for the exit vertices 2 and 3 will be equal (symmetrical cases). During the first move one can go to the exit vertex with the probability of 0.5 or to go to a vertex that's not the exit vertex with the probability of 0.5. In the first case the number of moves equals 1, in the second one it equals 3. The total mathematical expectation is counted as 2 / 5 × (1 × 0.5 + 3 × 0.5) + 3 / 5 × (1 × 0.5 + 3 × 0.5)

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/22/2019 17:57:52 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|