tester解です。

操作全体で頂点 \(v\) を選んだ回数を表す確率変数を \(X_v\) とします。期待値の線形性から答えは \(X_v\) の期待値 \(E[X_v]\) の総和です。

\(E[X_v]\) を求める際は、頂点 \(1,\ v\) を結ぶパス上の頂点以外を選んだ操作は無視していいので、

• 「わるい頂点」のうち頂点 \(1,\ v\) を結ぶパス上の頂点だけ選べる
• パス上の頂点がすべて黒色になるまで操作を行い、\(v\) が選ばれる回数を数える

という設定の下で考えても求まる値は同じです。

さらに、操作を続けている間、頂点 \(v\) が常に「わるい頂点」であることに注意すると

• 「わるい頂点」だけでなく「いい頂点」も選んでよい

という設定の下で考えても求める値は同じです（「いい頂点」を選んだ操作を無視すれば元の設定になります）。

すると求める値は「\(n\) 種類のアイテムでコンプガチャをする際、\(1\) 番目のアイテムを引く回数の期待値」に等しいです。コンプガチャでガチャを引く回数の期待値が \(n \sum_{i=1}^{n}\frac{1}{i}\) であるため、この答えは \(\sum_{i=1}^{n}\frac{1}{i}\) になります。

よってあらかじめ \(1\) から \(N\) までの逆数の累積和を求めておけば答えは \(O(N)\) で求めることができます。