← 返回题目列表

Codeforces · 123/E

E. 迷宫

中文机器翻译题面 查看原题

迷宫由树(无向图,每对顶点之间存在一条路)表示。在迷宫中,以一定的概率选择入口顶点和出口顶点。迷宫的出口是通过深度优先搜索来寻找的。如果有多种可能的移动方式,则以等概率选择移动。考虑以下伪代码:

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)