以下是我的推导

令 $E_i$ 表示从 $i$ 到 $n$ 的期望。

如果不考虑 $i$ 没有出边的情况，可以先粗略地写出 $E_i$ 的式子：

$$E_i = \sum_{E_j < E_i} E_j p_{i,j}\prod_{E_k < E_j}(1-p_{i,k})$$

设 $\displaystyle q = \prod_{E_j < E_i}(1-p_{i,j})$​ ，然后枚举在第 $i$​ 个点停留了 $k$​ 天：

$$\begin{aligned} &\sum_{k=1}^{+\infty}q^{k-1}(E+k)\\ =&\sum_{k=1}^{+\infty}kq^{k-1} + E\sum_{k=0}^{+\infty}q^{k}\\ =&{\color{Red} \frac{1}{(1-q)^2} } + E \frac{1}{1-q}\\ =&{\color{Red} \frac{1}{(1-q)^2} } + \sum_{E_j < E_i} \frac{E_j}{1-q} p_{i,j}\prod_{E_k < E_j}(1-p_{i,k}) \end{aligned}$$

---

然而，题解里的推出来的式子是这样的：

$$E_i = \sum_{E_j < E_i} \frac{E_j}{1-q} p_{i,j}\prod_{E_k < E_j}(1-p_{i,k}$$

比我的少了前面标红了的那一项。

我不知道我的推到哪步出错了，还请各路神仙帮忙看看QAQ