writer解です。コンテスト中の提出を見た限りだとtester解で解かれた方が圧倒的に多かったのでそちらを見たほうがいいかもしれません。

[1] 期待値の線形性の利用

\(k=0,\ 1,\ \dots,\ N-1\) に対して \(X_k\) を 黒い頂点数が初めて \(k\) 個になった瞬間から、黒い頂点数が初めて \(k+1\) 個になる瞬間までに行う操作回数をあらわす確率変数とします。期待値の線形性から \(\sum_{k=0}^{N-1} E[X_k]\) が答えです。

黒い頂点の数が変化しない間、「よい頂点」の数も変化しません。よって黒い頂点数が初めて \(k\) 個になった瞬間における「よい頂点」の数が \(m\) 個のときの \(X_k\) の（条件付き）期待値は \(\frac{1}{\frac{N-k}{N-m}}=\frac{N-m}{N-k}\) です。黒い頂点数が初めて \(k\) 個になった瞬間における「よい頂点」の数が \(m\) である確率を \(p_{k,m}\) とすると、このことから \(\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\) がわかります。よって\(\displaystyle \sum_{m=0}^{N}p_{k,m}m, \) すなわち黒い頂点数が初めて \(k\) 個になった瞬間における「よい頂点」の数の期待値が求まればいいです。

黒い頂点数が初めて \(k\) 個になった瞬間において、頂点 \(i\) が「よい頂点」である確率を \(q_{k,i}\) とおくと、「よい頂点」の数の期待値は、期待値の線形性から \(\sum_{i=1}^{N}q_{k,i}\) です。

[2] 白い頂点を選ぶ操作のみに着目

頂点 \(i\) の（自身を含む）祖先の数を \(d_i\) とおきます。

\(q_{k,i}\) を求めましょう。新しく黒色になる白い頂点はいずれの時点でも等確率で選ばれます。よって求める確率は \(N\) 個のボールから \(k\) 個のボールを一様ランダムに選ぶ際、指定された \(d_i\) 個のボールが含まれている確率に等しく 、\(d_i \leq k\) のとき \(\displaystyle q_{k,i}=\frac{\binom{N-d_i}{k-d_i}}{\binom{N}{k}}=\frac{k!(N-d_i)!}{N!(k-d_i)!}, \) そうでないとき \(0\) です 。

[3] NTTの利用

以上より各 \(k\) に対する \(\displaystyle \frac{k!}{N!} \sum_{1\le i \le N, d_i \le k} \frac{(N-d_i)!}{(k-d_i)!}\) が求まればいいです。

\(d_v=i\) を満たす \(v\) の数を \(c_i\) とおくと

\(\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)!}\)

これは \(f_i=c_i (N-i)!,\ g_i=\frac{1}{i!}\) の畳み込みの式になっているため、NTT を用いることで、すべての \(k\) に対する値が \(O(N\log N)\) で求まります。