[1] Use the linearity of expectation

For \(k=0,\ 1,\ \dots,\ N-1\), let \(X_k\) be a random variable representing the number of operations performed after there are \(k\) black vertices for the first time before there are \(k+1\) black vertices for the first time. From the linearity of expectation, the answer is \(\sum_{k=0}^{N-1} E[X_k]\).

While the number of black vertices does not change, neither does the number of good vertices. Thus, the (conditional) expected value of \(X_k\) when there are exactly \(m\) black vertices at the moment there are \(k\) black vertices for the first time is \(\frac{1}{\frac{N-k}{N-m}}=\frac{N-m}{N-k}\). From this, if \(p_{k,m}\) is the probability that there are exactly \(m\) good vertices at the moment there are \(k\) black vertices for the first time, it can be seen that \(\displaystyle E[X_k]=\sum_{m=0}^{N}\frac{p_{k,m}(N-m)}{N-k}=\frac{N}{N-k}-\frac{1}{N-k}\sum_{m=0}^{N}p_{k,m}m\). Therefore, it is enough to find \(\displaystyle \sum_{m=0}^{N}p_{k,m}m\), that is, the expected number of good vertices at the moment there are \(k\) black vertices for the first time.

If \(q_{k,i}\) is the probability that vertex \(i\) is good at the moment there are \(k\) black vertices for the first time, the expected number of good vertices is \(\sum_{i=1}^{N}q_{k,i}\) from the linearity of expectation.

[2] Focus on operations that choose white vertices

Let \(d_i\) be the number of ancestors of vertex \(i\) (including itself).

Let us find \(q_{k,i}\). The white vertex that turns black is always chosen with equal probability. Thus, the sought probability is equal to the probability that when \(k\) of \(N\) balls are chosen uniformly at random, some specified \(d_i\) balls are all chosen, which is \(\displaystyle q_{k,i}=\frac{\binom{N-d_i}{k-d_i}}{\binom{N}{k}}=\frac{k!(N-d_i)!}{N!(k-d_i)!}\) when \(d_i \leq k\) and \(0\) otherwise.

[3] Use NTT

Therefore, it is enough to find \(\displaystyle \frac{k!}{N!} \sum_{1\le i \le N, d_i \le k} \frac{(N-d_i)!}{(k-d_i)!}\) for each \(k\).

If \(c_i\) is the number of \(v\) such that \(d_v=i\), we have:

\(\displaystyle \sum_{1\le i \le N, d_i \le k} \frac{(N-d_i)!}{(k-d_i)!}= \sum_{i=1}^{k} c_i \frac{(N-i)!}{(k-i)!}.\)

This is the convolution of \(f_i=c_i (N-i)!\) and \(g_i=\frac{1}{i!}\), so one can find the values for all \(k\) in \(O(N\log N)\) time by using NTT.