Let’s consider the answer when \(M = 1\). In this case, Takahashi alternates between moving to one of the leaf vertices and returning to vertex \(0\). We can consider the operation of going to a leaf and returning to the root as a single unit called a round trip.

We consider the expected number of operations needed until all leaves are painted. When \(i\) leaves are already painted, the expected number of round trips needed until a new leaf is painted is \(\frac{N}{N - i}\). Thus, the expected number of round trips until all leaves are painted is the sum of \(\frac{N}{N - i}\) over \(i = 0, 1, \dots, N - 1\).

Each round trip requires \(2\) operations, and it is unnecessary to return to the root after all vertices are painted, so the answer is \(\left(\frac{N}{N} + \frac{N}{N - 1} + \dots + \frac{N}{2} + \frac{N}{1}\right) \times 2 - 1\).

Actually, we can handle a general \(M\) in the same way. Through some calculations, we find that the average number of operations per round trip is \(2M^2\), and the rest of the argument proceeds similarly. Thus, the answer is \(M^2\) times the answer for the case \(M = 1\).

• The fact that the expected number of operations per round trip is \(2M^2\) can be shown by focusing on the depth of the vertex where he is on. By considering the depth, we essentially solve the problem: “When performing a random walk on a path graph consisting of vertices \(0, 1, \dots, M\) connected in this order, what is the expected number of steps needed to reach vertex \(M\) from vertex \(0\) and then return to vertex \(0\)?” The answer to this problem is \(2M^2\).

Therefore, we have solved this problem. The computational complexity is about \(\mathrm{O}(N)\), which is sufficiently small.