设

• \(E_i\) 为树根到高度为 \(i\) 的点的期望用时
• \(Q_i\) 为 \(i-1\) 到 \(i\) 的概率，\(Q_i=1-P_i\)
• \(T_i\) 为 \(i-1\) 到 \(i\) 的期望用时，\(T_i=E_i-E_{i-1}\)

则有

\(T_i=Q_i \cdot 1 + (1-Q_i) \cdot (E_{i-1} + T_i)\)
\(\to E_i - E_{i-1} = Q_i + (1-Q_i) \cdot (E_{i-1} + E_i - E_{i-1})\)
\(\to E_i - E_{i-1} = Q_i + (1-Q_i) \cdot E_i\)
\(\to E_i - E_{i-1} = Q_i + E_i - Q_i \cdot E_i\)
\(\to Q_i \cdot E_i = Q_i + E_{i-1}\)

但是这样一来，\(E_0\) 等于多少？

所以换一种定义方式

设

• \(E_i\) 为高度为 \(i\) 的点到树顶的期望用时
• \(P_i\) 走到 \(i\) 点时会掉下去的概率

则有

\(E_i=1+P_{i+1} \cdot E_0+(1-P_{i+1}) \cdot E_{i+1}\)

且
\(E_n=0\)

观察到方程低阶E可以由高阶E表示，所以我们需要的答案也肯定可以由 \(E_n\) 表示
具体式子

code

太难了