2280: Maze
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
算法训练  Maze 
时间限制:1.0s    内存限制:256.0MB
   
问题描述
一个含有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将会统计移动的次数。
你的任务是统计一个人从这个迷宫的入口走到出口步数的数学期望值。
输入格式
第一行一个数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  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
样例说明
第一个样例中,入口总是1,出口总是2。
第二个样例的入口总是1且出口有2/5的概率是2,3/5的概率是3。对于出口为2和3的数学期望是相同的(对称的情况),第一步有0.5的概率直接  到达出口,0.5的概率走错到另一个点(然后再走两步到终点)。所以数学期望等于2/5*(1*0.5+3*0.5)+3/5*  (1*0.5+3*0.5)  =  2。
数据规模和约定
20%  的数据n  < =  100
50%  的数据n  < =  1000
70%  的数据n  < =  10000
100%的数据n  < =  100000
HINT
请关注微信公众号onlinejudge