题目描述

一个含有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

输入格式

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

输出格式

输出期望的步数，要求误差不超过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

输入格式
　　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

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

来源

蓝桥杯 算法训练