Problem L: Maze

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 搜索
一个含有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
1.00000000000000000000
输入格式 

1  2 
1  3 
1  0 
0  2
0  3 
输入格式 

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 
样例输出 
输出格式 
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