20250121T1 一道期望题

描述：

给一棵以 1 为根的有根树，你希望走到某个叶子节点。在非叶子节点，你下一步有的概率回到根节点，也可能随机向相邻节点走一步：具体地，设有个儿子，有的概率走到；当不是根节点时，有的概率走到的父亲节点。求从根节点走到叶子节点的期望步数。

思路：

这道题可以先设状态：设为从点走向叶子节点的期望步数。

这里先令为，即从点向下走的概率。这里为的儿子。

根据题目的定义，我们可以得到：

$f_x = h_x (f_{rt} + 1) + (1-h_x - g_x)\times(f_{fa} + 1) + \sum_{i=1}^{k} (f_v + 1)\cdot q_v$

然后进一步拆解这个式子得：

$\begin{aligned} f_x &= h_x\times f_{rt} + (1-h_x - g_x) \times f_{fa} + (\sum_{i=1}^{k}f_vq_v) + h_x + 1-h_x - g_x + g_x \\ &=h_x\times f_{rt} + (1-h_x-g_x)\times f_{fa} + (\sum_{i=1}^{k} f_vq_v) + 1 \end{aligned}$

特别地、 $叶子节点$ ，。

于是，我们将所有的都转化为了的形式（此处为常数）。然后我们就可以用高斯消元做了。

……

Over 了吗？高斯消元的算法复杂度是，你过是肯定不现实的。于是我们应该尝试优化这个算法。

观察这个式子可以知道，这些是可以从叶子节点一步一步推上来的。因为叶子节点的值都为。

为了使思路更清晰，先列一下式子：

$\begin{aligned} f_x &= A_x \cdot f_{rt} + B_x \cdot f_{fa_x} + C_x \\ &= h_x \cdot f_{rt} + (1-h_x - g_x) \cdot f_{fa} + (\sum_{i=1}^{k} f_vq_v )+ 1 &(1)\\ f_v &= A_v \cdot f_{rt} + B_v \cdot f_{x} + C_v &(2) \end{aligned}$

然后把式子带入式子得：

$\begin{aligned} f_x &= h_x \cdot f_{rt} + (1-h_x - g_x) \cdot f_{fa} + (\sum_{i=1}^{k} (A_v\cdot f_{rt} + B_v \cdot f_x + C_{v})q_v) + 1\\ f_x &= (h_x + \sum_{i=1}^{k} q_vA_v) \cdot f_{rt} + (1-h_x-g_x) \cdot f_{fa} + ((\sum_{i=1}^{k}q_v C_v) + 1) + (\sum_{i=1}^{k}q_vB_v)f_x \\ (1 - \sum_{i=1}^{k}q_vB_v)f_x &= (h_x + \sum_{i=1}^{k} q_vA_v) \cdot f_{rt} + (1-h_x-g_x) \cdot f_{fa} + ((\sum_{i=1}^{k}q_v C_v) + 1) \\ \end{aligned}$

于是我们就得出了关于的转移式子。

记住在当的时候最后要将。因为最后里面没有。

于是最后我们就得到了形如的式子。显然地、。于是这道题就做完了。

总结：

做期望的题首先是设状态。状态一般是分两种：
- 状态到目标状态的期望
- 状态到的下一步状态的期望
然后再列转移式子。这一步千万不要吝惜推式子！（就像这道题一样）但是也别方向都找错了在这推式子。
然后就会得到一个最终式子，这个式子一般是基于其它的状态。如果没有后效性，一般就用动态规划 DP。而如果有后效性，就用有后效性 DP 或者高斯消元法。（当然这道题其实是对高斯消元法的优化）

这道题重点在设状态和推式子，代码很短：

Code (1.05 KiB):

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct Edge{
    int to, nxt;
}edge[N<<1];
int head[N], cnt;
void add(int u, int v){
    edge[++cnt] = {v, head[u]};
    head[u] = cnt;
}
double A[N], B[N], C[N], h[N], q[N];
int n, fa[N];
void dfs(int x){
    int soncnt = 0;
    for(int i=head[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        dfs(v); soncnt ++;
    }
    if(soncnt == 0) return ;
    double D = 1;
    for(int i=head[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        A[x] += q[v] * A[v];
        B[x] += q[v];// g[x] += q[v];
        C[x] += q[v] * C[v];
        D -= q[v] * B[v];
    }
    A[x] += h[x], B[x] = 1-h[x]-B[x], C[x] += 1;
    A[x] /= D, B[x] /= D, C[x] /= D;
    if(fa[x] == 1) A[x] += B[x], B[x] = 0;
}
int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        add(fa[i], i);
    }
    for(int i=2;i<=n;i++) cin>>q[i];
    for(int i=1;i<=n;i++) cin>>h[i];
    dfs(1);
    double ans = C[1] / (1-A[1]);
    printf("%.2lf", ans);
    return 0;
}