ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
9233: 逃跑
内存限制:128 MB
时间限制:1 S
题面:传统
评测方式:文本比较
上传者:
提交:0
通过:0
提交
提交记录
统计
Web Board
题目描述
小明所在星系有 $n$ 颗星球,编号为 $1$ 到 $n$。这些星球通过 $n-1$ 条无向边连成一棵树。根结点为编号为 $1$ 的星球。 为了在星际战争到来时逃到其他星系,小明在根结点设置了逃离用的传送门。每个星球的人只需要一直往父结点星球移动就可以抵达根结点。为了方便各个星球的人去往根结点,小明将其中 $m$ 个星球设置为了跳板星球。在从某个星球去往根结点的路径上,当一个人经过任意星球(包括起点星球)时,他可以尝试直接跳跃到 **其前往根结点路径上的除当前星球以外的第一个跳板星球**,其时间花费和走到父结点星球的时间花费相同,都是 $1$ 单位时间。 然而,因为技术问题,向跳板星球的跳跃并不一定成功,每一次跳跃都有 $p$ 的概率失败,并转而跳跃到当前星球的父结点星球(相当于直接走到父结点星球);同时此跳板星球失效,将 **不再视为跳板星球**。 为了衡量移动效率,小明想知道,如果一个人在这 $n$ 颗星球中随机选择一颗出发前往根结点,其花费的最短时间的期望是多少单位时间?
输入格式
输入共 $n + 1$ 行,第一行为两个正整数 $n$、$m$ 和一个浮点数 $p$。 后面 $n - 1$ 行,每行两个正整数 $x_i,y_i$ 表示第 $i$ 条边的两个端点。 最后一行,共 $m$ 个正整数表示所有跳板星球的编号。
输出格式
一行,一个浮点数,表示答案(请保留两位小数)。
输入样例
复制
4 1 0.2 1 2 2 3 3 4 2
输出样例
复制
1.30
数据范围与提示
从 $1$ 号星球出发的时间花费为 $0$; 从 $2$ 号星球出发的时间花费为 $1$; 从 $3$ 号星球出发的时间花费为 $2$; 从 $4$ 号星球出发的时间花费为 $0.8 \times 2 + 0.2 \times 3 = 2.2$。
分类标签
2023
蓝桥
国赛
p9428