\(G\) の中のある連結成分 \(G'\) について考えます。\(G'\) を \(N'\) 頂点とした場合、辺数も \(N'\) であるため \(G'\) にはサイクルが \(1\) 個だけ存在します。

よって、連結成分数の代わりにサイクル数を数え上げることとします。

まず、\(A_i \neq -1\) である \(i\) に対して辺を貼った場合に出来ているサイクルを数えておきます。

その後、上記の連結成分以外は木となっています。それらに \(1,2,\dots,K\) と番号をつけ、\(i\) 番の連結成分のサイズを \(B_i\) と置きます。

\(1 \le x_1 < x_2 < \dots < x_k \le K\) に対して、番号 \(x_1,x_2,\dots,x_k\) の連結成分の頂点が含まれるサイクルの個数を求めます。これは \((k-1)! \times \prod_{i=1}^{k} B_{x_i}\) となります。

よって、\(k\) ごとに \(\prod_{i=1}^{k} B_{x_i}\) の総和を動的計画法で求めることによってこの問題は \(\mathrm{O}(N^2)\) で解くことができます。

また、\(\prod_{i=1}^{K} (1 + B_ix)\) を分割統治で計算することで \(\mathrm{O}(N\log^2 N)\) で解くことも可能です。