\(M = 1\) の場合の答えを考えてみましょう。この場合、高橋君は葉の頂点のいずれかに移動する操作と頂点 \(0\) に戻る操作を交互に繰り返します。この葉に行って根に戻るまでの操作を 往復 と呼んでひとまとまりの操作として考えることにします。

全ての葉に色が塗られるまでにかかる回数の期待値を考えます。色が塗られた葉が \(i\) 枚の時、次に新たに色が塗られるまでに必要な往復の回数の期待値は \(\frac{N}{N-i}\) 回です。よって全ての葉に色が塗られるまでにかかる回数の期待値は \(\frac{N}{N-i}\) を \(i=0,1,\dots,N-1\) について足し合わせたものになります。

\(1\) 往復に \(2\) 回の操作が必要なこと、および全ての頂点に色がついた後に根に戻る操作は不要であることから、答えは \(\left(\frac{N}{N} + \frac{N}{N-1} + \dots + \frac{N}{2} + \frac{N}{1}\right) \times 2 - 1\) 回になります。

実は \(M\) が一般の場合でも同様に解くことが出来ます。というのも、いくらかの計算により \(1\) 往復あたり平均 \(2M^2\) 回の操作が必要であることが確認できて、それ以外は同様の議論が成り立つからです。よって答えは \(M=1\) の場合の答えを \(M^2\) 倍したものになります。

• 往復にかかる操作回数が平均 \(2M^2\) 回であることは、高橋君がいる頂点の深さに注目することで示せます。頂点の深さに注目すると、結局「頂点 \(0\), 頂点 \(1\), \(\dots\), 頂点 \(M\) がこの順につながったパスグラフ上をランダムウォークするとき、頂点 \(0\) から頂点 \(M\) に到達して頂点 \(0\) に戻ってくるまでの回数の期待値は？」という問題を解くことになり、この問題の答えは \(2M^2\) になります。

以上でこの問題を解くことが出来ました。計算量は \(\mathrm{O}(N)\) 程度で十分高速です。