说明

算法训练&nbsp Maze&nbsp  

时间限制：1.0s&nbsp  &nbsp 内存限制：256.0MB

 &nbsp  &nbsp

问题描述

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

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

　　DFS(x)

　　if&nbsp x&nbsp ==&nbsp exit&nbsp vertex&nbsp then

　　finish&nbsp search

　　flag[x]&nbsp < -&nbsp TRUE

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

　　for&nbsp i&nbsp < -&nbsp 1&nbsp to&nbsp length[V]&nbsp do

　　if&nbsp flag[V[i]]&nbsp =&nbsp FALSE&nbsp then

　　count++;

　　DFS(y);

　　count++;

　　V(x)是与x点相邻的点的序列。Flag数组初始时是全部为FALSE的。DFS&nbsp 初始时从入口开始。当搜索结束时，变量count将会统计移动的次数。

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

输入格式

　　第一行一个数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。

输出格式

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

样例输入

输入格式

　　2

　　1&nbsp 2

　　0&nbsp 1

　　1&nbsp 0

输入格式

　　3

　　1&nbsp 2

　　1&nbsp 3

　　1&nbsp 0

　　0&nbsp 2

　　0&nbsp 3

输入格式

　　7

　　1&nbsp 2

　　1&nbsp 3

　　2&nbsp 4

　　2&nbsp 5

　　3&nbsp 6

　　3&nbsp 7

　　1&nbsp 1

　　1&nbsp 1

　　1&nbsp 1

　　1&nbsp 1

　　1&nbsp 1

　　1&nbsp 1

　　1&nbsp 1

样例输出

输出格式

　　1.00000000000000000000

输出格式

　　2.00000000000000000000

输出格式

　　4.04081632653

样例说明

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

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

数据规模和约定

　　20%&nbsp 的数据n&nbsp < =&nbsp 100

　　50%&nbsp 的数据n&nbsp < =&nbsp 1000

　　70%&nbsp 的数据n&nbsp < =&nbsp 10000

　　100%的数据n&nbsp < =&nbsp 100000