概要

公式解説の記法を借ります。

\(p(i)\) は二分木上に畳みこむことで \(\mathrm{O}(N\log^2N)\) で求まります。

\(q(i)\) はLagrange 反転を用いた 2-edge connected graphs の数え上げ、及び 固定された \(k\) に対して、\([x^k] f^i(x)\) を各 \(i\) について列挙するLagrange 反転を用いたテクを用いることで、 \(\mathrm{O}((N\log N)^{1.5})\) で計算できます。

これらにより、時間計算量 \(\mathrm{O}((N\log N)^{1.5})\) の解法が得られます。

---

公式解説と基本的な方針は同じかと思われますが、方針をまず記します。

積の和典型と対称性を用いると、\(k=1,2,\ldots,N\) に対して、\(\prod_{i=1}^k A_i\) が何回答えに寄与するかが求まればよいです。

まず、\(k\) を固定した場合を考えます。

二辺連結成分を縮約したグラフが木となっており、その木の頂点数が \(k\) 個となっている必要があります。 更に、頂点 \(1\) から頂点 \(k\) は縮約後の頂点が異なる必要があります。

これらの条件を満たす数え上げを考えましょう。

まず、縮約後の頂点について、元のグラフで頂点 \(i\) が含まれているものを頂点 \(i'\) と呼ぶことにします。また、頂点 \(i'\) が含む縮約前の頂点数を以下頂点 \(i'\) の サイズ と呼ぶこととします。

頂点のサイズを \(c_1,c_2,\ldots,c_k\) と固定し、頂点番号の割り当て方を考えることとします。

頂点 \(i'\) の一つの頂点の頂点番号は既に頂点 \(i\) と定まっていて、\(c_i-1\) 個の頂点番号はまだ未定であり、頂点 \(k+1\) から頂点 \(N\) を割り当てる必要があります。

割り当て方法はこの考察から多項係数 \(\binom{N-k}{c_1-1, c_2-1,\ldots,c_k-1}\) と表されます。

次に各頂点 \(i'\) の縮約前の辺の張られ方を考えます。これは、\(c_i\) 頂点の橋を持たない連結な単純グラフの総数 \(f_{c_i}\) に等しいです。

\(f_1,f_2,\ldots,f_N\) の列挙はnoshi91 さんの tweet の手法により \(\mathrm{O}((N\log N)^{1.5})\) で可能です。

最後に、縮約後の頂点間を結んで木にする方法の総数を数え上げます。これは、Prüferコードを用いた考察により \(\prod_{i=1}^k c_i N^{k-2}\) と求まります。

以上を整理します。\(k, c_1,c_2,\ldots,c_k\) を固定したときの \(\prod_{i=1}^k A_i\) の寄与回数は、以下の式で表されます。

\[ \binom{N-k}{c_1-1, c_2-1,\ldots,c_k-1} N^{k-2}\prod_{i=1}^k c_i f_{c_i} = (N-k)!N^{k-2} \prod_{i=1}^k \frac{c_if_{c_i} }{(c_i-1)!} \]

\(c_1,c_2,\ldots,c_k\) 全てに対する総和を取るのは、上の式まで整理できていればFPS を用いて簡単に行えます。

\(F(x) = \sum_{i=1}^N \frac{if_i}{(i-1)!}x^i\) と置けば、先ほどの式の全ての \(c\) に対する総和は

\[(N-k)!N^{k-2} [x^N] F^k(x)\]

と求まります。後は、全ての \(k=1,2,\ldots,N\) に対して \([x^N] F^k(x)\) が高速に求まればよいです。これも、先ほどのブログにて \(\mathrm{O}((N\log N)^{1.5})\) で求める方法が記述されています。

以上でこの問題を解くことができました。