跳至正文
题库4090
#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。

来源

蓝桥杯 算法训练