結局、初めて葉に着くまでの回数の期待値が求まれば答えは簡単に求まります。

これは \(M^{2}\) であると公式解説に書いてあるのですが、そのような具体的な値が分からなくても答えを求めることができます。

\(A_{i}\) を深さ \(i\) のところから始めて、初めて葉に着くまでの回数の期待値であるとします。

このとき、以下の関係式が成り立ちます。

• \(A_{0} = A_{1} + 1\)
• \(A_{1} = 1 + \frac{A_{0} + A_{2}}{2}\)
• \(A_{2} = 1 + \frac{A_{1} + A_{3}}{2}\)
• \(\cdots\)
• \(A_{M - 1} =1 + \frac{A_{M - 2} + A_{M}}{2}\)
• \(A_{M} = 0\)

上の式から順番に見ることで、 \(A_{i} - A_{0}\) の値が順にわかります。最後に \(A_{M} - A_{0}\) の値がわかるので、\(A_{M} = 0\) を用いることで、\(A_{0}\) の値がわかります。

それが求まればその値に \((1 + 2\sum_{i = 2}^{N}\frac{N}{i})\) をかければ答えが出ます。