Description

一个含有n个点的迷宫是一棵树（一个任意两点之间都恰好有一条路径的无向图）。每个点都有一定的概率成为这个迷宫的入口和出口。

从这个迷宫走出去的方法是从入口开始进行深度优先搜索。如果当前有多个移动方案，那么等概率的选择移动方案中的一个。DFS的过程为以下的伪代码：

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)是与x点相邻的点的序列。Flag数组初始时是全部为FALSE的。DFS 初始时从入口开始。当搜索结束时，变量count将会统计移动的次数。

你的任务是统计一个人从这个迷宫的入口走到出口步数的数学期望值。

Input Format

第一行一个数n，表示这个图的节点数。。

下面n-1行，每行包括两个数ai,bi，表示一条连接ai和bi的边。

保证给出的图是一棵树。

下面n行，每行包括两个非负整数xi,yi，表示选择i为入口的可能性和出口的可能性。

选择i为入口的概率和选择i为出口的概率分别为 xi/sumx和yi/sumy，sumx表示x的总和，sumy表示y的总和。sumx以及sumy均为正数且不超过$10^6$。

Output Format

输出期望的步数，要求误差不超过$10^{-9}$。

2
1 2
0 1
1 0

3 
1 2 
1 3
1 0
0 2
0 3

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

1.00000000000000000000

2.00000000000000000000

4.04081632653

Hint

样例说明

第一个样例中，入口总是1，出口总是2。

第二个样例的入口总是1且出口有2/5的概率是2，3/5的概率是3。对于出口为2和3的数学期望是相同的（对称的情况），第一步有0.5的概率直接 到达出口，0.5的概率走错到另一个点（然后再走两步到终点）。所以数学期望等于2/5*(10.5+30.5)+3/5* (10.5+30.5) = 2。

数据规模和约定

20% 的数据n <= 100

50% 的数据n <= 1000

70% 的数据n <= 10000

100%的数据n <= 100000

Source

蓝桥杯