#4090
Maze
Maze
题目描述
一个含有 n 个点的迷宫是一棵无向树。每个点都有一定概率成为入口或出口,入口和出口独立选择,也可以是同一个点。
从入口进行深度优先搜索。如果当前有多个相邻点,则先将它们的访问顺序随机打乱,所有排列等概率。以下伪代码定义具体过程:
DFS(x):
if x == exit:
finish the entire search immediately
flag[x] = TRUE
V = a uniformly shuffled list of all neighbors of x
for i = 1 to length(V):
if flag[V[i]] == FALSE:
count += 1
DFS(V[i])
count += 1
flag 初始全部为 FALSE,count 初始为 0。每经过一条边(包括回到父节点)计一步;到达出口时立即结束整个搜索,不再计返回的步数。求从入口到出口所经过步数的数学期望。
输入格式
第一行一个整数 n(1 ≤ n ≤ 100000)。接下来 n−1 行,每行两个整数 a、b(1 ≤ a、b ≤ n),表示一条无向边,保证图是一棵树。
接下来 n 行,每行两个非负整数 x_i、y_i。点 i 作为入口的概率为 x_i / sumx,作为出口的概率为 y_i / sumy,其中 sumx 和 sumy 分别是所有 x_i 和 y_i 的和,均在 [1, 1000000] 内。
输出格式
输出一个有限实数,表示期望步数。与正确答案的绝对误差不得超过 10−9。
样例
2
1 2
0 1
1 0
1.00000000000000000000
3
1 2
1 3
1 0
0 2
0 3
2.00000000000000000000
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
4.04081632653
说明/提示
样例 1 的入口总是点 2,出口总是点 1,经过一步即可到达。样例 2 的入口总是点 1;出口以 2/5 和 3/5 的概率分别为点 2 和点 3。对每个出口,都有一半概率经过 1 步,一半概率经过 3 步,所以期望为 2。
20% 的数据 n ≤ 100;50% 的数据 n ≤ 1000;70% 的数据 n ≤ 10000;100% 的数据 n ≤ 100000。