比赛场次 244
比赛名称 难度范围:提高至省选
比赛状态 已结束比赛成绩
开始时间 2014-10-16 17:35:00
结束时间 2014-10-16 20:00:00
开放分组 全部用户
注释介绍 犇们不要去做普及水题赛卖萌,谢谢
题目名称 树状迷宫
输入输出 cf123e_maze.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 50 评测插件
用户 结果 时间 内存 得分
Gravatarcstdio AAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAA
AAAAAAAAAA
0.831 s 4.42 MiB 100

树状迷宫

★★★   输入文件:cf123e_maze.in   输出文件:cf123e_maze.out   评测插件
时间限制:1 s   内存限制:256 MiB

【题目描述】

一个迷宫是一棵树(即一张无向图,其中任意两点之间仅有一条路径)。迷宫的起点和终点都按照某种概率随机选取。人们会在迷宫中用深度优先搜索的方法搜寻终点。如果有许多条可能的路径,会等概率地选取一条。考虑如下伪代码:

DFS(x)
    if x == exit vertex then
        finish search
    flag[x] <- TRUE
    // here all permutations have equal probability to be chosen
    random shuffle the vertices' order in V(x) 
    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(1 \leq n \leq 10^5)$。接下来 $n-1$ 行每行有一对整数 $a_i$ 和 $b_i$,代表顶点 $a_i$ 和 $b_i$ 之间有一条边 $(1 \leq a_i,b_i \leq n)$。保证所给的图是一棵树。

接下来的 $n$ 行每行有两个非负整数 $x_i,y_i$,起点 $i$ 被选为入口的概率是 $x_i/∑x_i$,被选为出口的概率是 $y_i/∑y_i$。$∑x_i$ 和 $∑y_i$ 都不超过 $10^6$。

【输出格式】

输出一行一个实数,即步数的期望值。你程序输出与标准输出的相对误差不能超过 $10^{-9}$。

【样例输入】

样例输入1:
2
1 2
0 1
1 0

样例输入2:
3
1 2
1 3
1 0
0 2
0 3

样例输入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:
1.00000000000000000000

样例输出2:
2.00000000000000000000

样例输出3:
4.04081632653

【提示】

在第一组样例中,入口总是 $1$,出口总是 $2$.

在第二组样例中,入口总是 $1$,出口有 $2/5$ 的可能性是 $1$,有 $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)$。

【来源】

CODEFORCES 123E