题解：P9428 [蓝桥杯 2023 国 B] 逃跑
BaiBaiShaFeng
·
·
题解
题解：P9428 [蓝桥杯 2023 国 B] 逃跑
高一蒟蒻刚学完概率期望，整篇简单题。
题意：
要去根节点，中途有跳板星球可以直接跳到跳板星球，但有一定概率失败，求最短时间期望。
想必能到这里大概都对于期望有一定了解，若不会建议先去学学。依照我的见解，概率动态规划仅仅是套了个概率论的包装罢了，我们利用它解决问题即可。
OIWIKI
思路
存图我们就不多说了，这里我使用的是我最喜欢的链式前向星存图。
为了让大家更好理解样例，我决定手模一下。
所给样例↓
```
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 相信大家都明白，就不说了。
### 代码
```cpp
#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;
}
```