自动搬运

查看原文

来自洛谷，原作者为

	BaiBaiShaFeng 我喜欢的不是晚霞，是引得我抬头的人

搬运于2025-08-24 22:48:16，当前版本为作者最后更新于2025-03-30 16:48:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：P9428 [蓝桥杯 2023 国 B] 逃跑

高一蒟蒻刚学完概率期望，整篇简单题。

题意：

要去根节点，中途有跳板星球可以直接跳到跳板星球，但有一定概率失败，求最短时间期望。

想必能到这里大概都对于期望有一定了解，若不会建议先去学学。依照我的见解，概率动态规划仅仅是套了个概率论的包装罢了，我们利用它解决问题即可。

OIWIKI

思路

$n$ 点 $n-1$ 条边，显然这是个树。

存图我们就不多说了，这里我使用的是我最喜欢的链式前向星存图。

为了让大家更好理解样例，我决定手模一下。

所给样例↓

4 1 0.2
1 2
2 3
3 4
2

所给树拥有四个点，形成了一条链，我们正好方便分析。

• 从 $1$ 号星球出发，不需要移动，时间花费为 $0$。

• 从 $2$ 号星球出发，直接到根结点，时间花费为 $1$。

• 从 $3$ 号星球出发，先到 $2$ 号星球，再到 $1$ 号星球，时间花费为 $2$。

• 从 $4$ 号星球出发：有 $0.8$ 的概率成功跳到 $2$ 号星球，再到 $1$ 号星球，时间花费为 $2$。还有 $0.2$ 的失败概率，先到 $3$ 号星球，再到 $2$ 号星球，最后到 $1$ 号星球，时间花费为 $3$。期望时间为 $0.8×2+0.2×3=2.2$。

最后咱们再汇总一下。

得出答案为 $\frac{0+1+2+2.2}{4}=1.30$。

我们可以很轻易地用动态规划轻易求解出每个节点的期望时间。

• 若当前的点是跳板星球，则下一个点的动态规划值直接为当前点的动态规划值加一即可。

这个好理解，跳不跳无人在意，没有任何区别。

• 若当前的点不是跳板星球，则下一个点的动态规划值为当前节点的动态规划值等于当前节点的动态规划值加上 $p^{num}$，其中 $p$ 是跳跃失败的概率，$num$ 是从当前星球到根结点路径上的跳板星球数量。

这个有一点难想，当从下一个点出发前往根时，因为当前星球不是跳板星球，所以下一个节点必须先到达当前节点，这一步的时间花费包含在当前节点的动态规划值里。接下来，从当前节点继续前往根结点的过程中，会遇到路径上的 $num$ 个跳板星球。对于每一个跳板星球，都存在成功和失败两种情况。要想让从下一个节点到根结点的时间最短，最好的情况是在经过所有跳板星球时都能成功跳跃。但实际上，每次跳跃都有 $p$ 的概率失败。

如果在经过跳板星球时至少有一次成功跳跃，那么花费的时间不会超过直接走到父结点再到根结点的时间，因为成功跳跃相当于抄近路，所以这种情况对最短时间期望的额外增加时间为 $0$。

由于每次跳跃失败的事件是相互独立的，根据乘法原理，连续 $num$ 次跳跃都失败的概率就是 $p^{num}$。

当连续 $num$ 次跳跃都失败时，就相当于没有利用任何跳板星球的跳跃功能，只能一步步地从当前星球走到父结点，最终到达根结点。这种情况下，相对于成功利用跳板星球跳跃的理想情况，额外多花费的时间期望就是 $p^{num}$。

本人第一篇题解，求通过。

若讲的哪里不清楚请评论留言，会更改。

具体的 dfs 相信大家都明白，就不说了。

代码

#include <bits/stdc++.h>
using namespace std;
const int MN=5e6+116;
struct Node{int nxt, to;}node[MN];
int head[MN], tottt, n, m;
inline void insert(int u, int v){
    node[++tottt].to=v;
    node[tottt].nxt=head[u];
    head[u]=tottt;
}
double p, dp[MN];
int gogogo[MN], num;
double quick_power(double a, int b){
    double res=1;
    while(b){
        if(b&1) res*=a;
        a*=a; b>>=1;
    }return res;
}
void dfs(int u, int father){
    if(gogogo[u]) ++num;
    for(int i=head[u];i;i=node[i].nxt){
        int v=node[i].to;
        if(v==father) continue;
        if(gogogo[u]) dp[v]=dp[u]+1;
        else dp[v]=dp[u]+quick_power(p,num);
        dfs(v,u);
    }if(gogogo[u]) num--;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n>>m>>p;
    for(int i=1,u,v; i<n; ++i){
        cin>>u>>v; insert(u,v); insert(v,u);
    }for(int i=1,point; i<=m; ++i){
        cin>>point; gogogo[point]=1;
    }
    dfs(1,0);
    double ans=0;
    for(int i=1; i<=n; ++i){
        ans+=dp[i];
    }
    cout<<fixed<<setprecision(2)<<ans/n<<'\n';
    return 0;
}