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

· · 题解

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

坑点：

  1. 跳跃是向跳板星球的。
  2. 其前往根结点路径上的除当前星球以外的第一个跳板星球。
  3. 求的是其花费的最短时间的期望。

    思路

    考虑递推，设当前节点为 u，它的子节点为 v。

易发现当 u 为跳板星球时，dp_{v}=dp_{u}+1。因为我们是求的其花费的最短时间的期望。

又因 0<p<1 所以不跳是更优的。

当 u 不为跳板星球时，计 cnt 为当前节点前往根结点路径上的跳板星球的个数。

有 dp_{v}=dp_{u}+p^{cnt}×1。

又因求其花费的最短时间的期望，所以要跳就一直跳，要么不跳，走到父节点。

Code

#include<bits/stdc++.h>
#define double long double
using namespace std;
const int N=1e6+6;
vector<int> g[N];
bool is[N];
int n,m,cnt;
double dp[N];
double p;
void dfs(int x,int fa,int cnt){
    if(is[x]) cnt++;
    for(int y:g[x]){
        if(y==fa) continue;
        if(is[x]) dp[y]=dp[x]+1;
        else dp[y]=dp[x]+pow(p,cnt);
        dfs(y,x,cnt);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    cin>>n>>m>>p;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        is[x]=1;
    }
    dfs(1,0,0);
    double sum=0;
    for(int i=1;i<=n;i++) sum+=dp[i];
    double ans=sum/n;
    printf("%.2Lf",ans);
}