顺推中，正确的转移方程： f[v] += (p[u] * w[i] + f[u]) / dout[u];

其中f[x]表示从1到x到期望步数，p[x]表示从1走到x的概率。

错误的转移式子是：

f[v] += p[u] / dout[u] * w[i] + f[u]

这样看似是对的，但是从定义出发：

对于v，它的期望步数是所有路径的概率乘上长度的和。

假设从1到u的所有路径是d1(p1), d2(p2), d3(p3)，d是长度，p是概率。

那么

f[v]=(d1+w)*p1/k + (d2+w)*p2/k + ... 
=1/k*(d1*p1+d2*p2+...+w*(p1+p2+...))
=1/k*(f[u]+w*p[u])

所以前者才是正确的

PS：错了这个只有20pts