P4316 绿豆蛙的归宿
原题
这篇帖子主要解释为什么正推和倒推有区别，如果想询问做法，请移步至洛谷题解区
倒推：\(dp_i\)表示从\(i \rightarrow n\)的期望距离，\(deg_u\)表示\(u\)点出度
\[dp_u = \sum_{(u,v,w) \in E}{\frac{dp_v + w}{deg_u}}
\]
正推：\(dp_i\)表示从\(1 \rightarrow i\)的期望距离，\(g_i\)表示\(1 \rightarrow i\)的概率，\(deg_u\)定义同上
\[dp_u = \sum_{(v,u,w) \in E}{\frac{(dp_v + w) \times g_v}{deg_v}}
\]
解释一下为什么正推会乘上一个系数\(g_v\)
倒推：
\[\begin{align}
E(v) &= \sum{p_i x_i} \\
E(u) &= \sum{p_i (x_i + w)} \\
&= \sum{p_i x_i} + \sum{p_i w} \\
&= E(v) + w
\end{align}
\]
因为从\(i\)走到\(n\)的概率之和为1
正推：
\[\begin{align}
E(u) &= \sum{p_i x_i} \\
E(v) &= \sum{p_i (x_i + w)} \\
&= \sum{p_i x_i} + \sum{p_i w} \\
&\neq E(v) + w
\end{align}
\]
因为从\(1\)走到\(i\)的概率之和不为1
因此扩展到一般情况，当在\(DAG\)上处理关于期望/概率的问题时，我们要先思考倒着做，因为这样可以多一个保证\(\sum{p_i} = 1\)的限制条件