#Pold1252. 算法训练 Maze

    ID: 575 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>蓝桥杯-算法训练赛制:ACM来源:蓝桥杯练习系统 ID: 343 原题链接: http://lx.lanqiao.cn/problem.page?gpid=T343搜索概率期望

算法训练 Maze

算法训练 Maze

题目描述

一个含有n个点的迷宫是一棵树(一个任意两点之间都恰好有一条路径的无向图)。每个点都有一定的概率成为这个迷宫的入口和出口。   从这个迷宫走出去的方法是从入口开始进行深度优先搜索。如果当前有多个移动方案,那么等概率的选择移动方案中的一个。DFS的过程为以下的伪代码:   DFS(x)   if x == exit vertex then   finish search   flag[x] <- TRUE   random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen   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,表示这个图的节点数。。   下面n-1行,每行包括两个数ai,bi,表示一条连接ai和bi的边。   保证给出的图是一棵树。   下面n行,每行包括两个非负整数xi,yi,表示选择i为入口的可能性和出口的可能性。

  选择i为入口的概率和选择i为出口的概率分别为xi/sumx和yi/sumy,sumx表示x的总和,sumy表示y的总和。sumx以及sumy均为正数且不超过10^6。 输入样例:

输出格式

输出描述:   输出期望的步数,要求误差不超过10^-9。 输出样例:

数据范围

(原站未提供,导入后需人工补齐)

样例

参考上文 
参考上文

提示

HINT:时间限制:1.0s 内存限制:256.0MB   2   1 2   0 1   1 0