Here is a tester’s solution.

Let \(X_v\) be a random variable representing the total number of times vertex \(v\) is chosen. From the linearity of expectation, the answer is the sum of \(E[X_v]\), the expected value of \(X_v\).

When finding \(E[X_v]\), we may ignore operations choosing vertices other than the ones on the path connecting vertices \(1\) and \(v\), so let us consider the number of times \(v\) is chosen under the following settings without changing the result.

• Only bad vertices on the path connecting vertices \(1\) and \(v\) can be chosen.
• The operation is repeated until all vertices on the path are black.

Furthermore, by noting that vertex \(v\) is always bad while repeating the operation, we may also consider under the following setting without changing the result.

• Not only bad vertices but also good vertices can be chosen.

(This would be the same as the original setting if we ignore operations that choose good vertices.)

Then, if we consider repeatedly drawing a lottery that awards \(n\) kinds of items, the sought value is equal to the expected number of times we get the first kind of item until getting everything at least once. Since the expected number of total draws is \(n \sum_{i=1}^{n}\frac{1}{i}\), the sought value is \(\sum_{i=1}^{n}\frac{1}{i}\).

Therefore, by pre-computing the accumulated sums of reciprocals of \(1\) through \(N\), the answer can be found in \(O(N)\) time.