迷宫由树(无向图,每对顶点之间存在一条路)表示。在迷宫中,以一定的概率选择入口顶点和出口顶点。迷宫的出口是通过深度优先搜索来寻找的。如果有多种可能的移动方式,则以等概率选择移动。考虑以下伪代码:
V(x) 是与 x 相邻的列表顶点。标志数组最初填充为 FALSE。 DFS 最初以入口顶点的参数开始。搜索完成后,变量 count 将包含移动次数。
你的任务是计算退出迷宫所需移动次数的数学期望。
输入
第一行确定图 n 中的顶点数 (1 ≤ n ≤ 105)。接下来的 n - 1 行包含整数对 ai 和 bi,这表明 ai 和 bi 顶点之间存在一条边(1 ≤ ai,bi ≤ n)。保证给定的图是一棵树。
接下来的 n 行包含非负数对 xi 和 yi,分别表示选择第 i 个顶点作为入口和出口的概率。选择顶点 i 作为入口和出口的概率相应地等于 $$x_i / \sum_{j=1}^{n} x_j$$ 和 $$y_i / \sum_{j=1}^{n} y_j$$。所有 xi 的总和与所有 yi 的总和均为正数且不超过 106。
输出
打印移动次数的期望。绝对或相对误差不应超过10-9。
示例
输入 #1
2 1 2 0 1 1 0
输出 #1
1.00000000000000000000
输入 #2
3 1 2 1 3 1 0 0 2 0 3
输出 #2
2.00000000000000000000
输入 #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
输出 #3
4.04081632653
注意
在第一个示例中,入口顶点始终为 1,出口顶点始终为 2。
在第二个示例中,入口顶点始终为 1,出口顶点的概率为 2/5,则为 2,如果概率为 3/5,则出口顶点为 3。出口顶点 2 和 3 的数学期望将相等(对称情况)。在第一次移动期间,可以以 0.5 的概率到达退出顶点,或者以 0.5 的概率到达不是退出顶点的顶点。在第一种情况下,移动次数等于 1,在第二种情况下,移动次数等于 3。总的数学期望计算为 2 / 5 × (1 × 0.5 + 3 × 0.5) + 3 / 5 × (1 × 0.5 + 3 × 0.5)