题解：P9428 [蓝桥杯 2023 国 B] 逃跑
wanganze
·
·
题解
题意
有一棵 n 个点的树，上面有 m 个标记的节点。一个单位时间有两种移动方式：走到父亲；以 p 的概率跳到最近的标记祖先，以 1-p 的概率走到父亲且最近的标记祖先失效。求最优策略下从每个点出发到根的时间的期望。
分析
设 $f_u$ 为当前节点 $u$ 走到根的时间的期望。
考虑 $u$ 的孩子 $x$。
如果 $u$ 是一个标记节点，那么在 $x$ 跳是没有意义的，无论如何也要走一步到 $u$，所以 $f_x=f_u+1$。
否则 $u$ 没有标记。讨论从 $x$ 往上跳能否成功。从 $x$ 往上跳如果成功至少一次，那么一定选择往上跳，而成功的概率和从 $u$ 往上跳是一样的，只和 $u$ 被标记的祖先数 $c$ 有关，为 $1-p^c$，需要步数的期望也一样；如果从 $x$ 往上跳全部失败，需要比从 $u$ 往上跳全部失败的情况多一步，概率为 $p^c$。所以 $f_x=(1-p^c)f_u+p^c(f_u+1)=f_u+p^c$。
## 实现
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long double LD;
const int N = 1e6 + 10;
vector<int> e[N];
bool st[N];
LD f[N],p;
void dfs(int u,int fa,LD q)
{
if(st[u]) q *= p;
for(int x : e[u])
{
if(x == fa) continue;
if(st[u]) f[x] = f[u] + 1;//跳板就一步，没有必要跳
else f[x] = f[u] + q;//跟当前节点成功概率一样所以时间一样，或者每次都跳失败了要多走一步
dfs(x,u,q);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m>>p;
for(int i = 1,x,y; i < n; i ++) cin>>x>>y,e[x].push_back(y),e[y].push_back(x);
for(int i = 1,x; i <= m; i ++) cin>>x,st[x] = 1;
dfs(1,0,1);
LD res = 0;
for(int i = 1; i <= n; i ++) res += f[i];
printf("%.2Lf",res / n);
return 0;
}
```