Ex - We Love Forest Editorial by Nyaan


ユーザー解説です

この問題は \(\mathrm{O}(2^N N^2)\) で解けます。簡潔に説明します。

前提知識:Subset Convolution (Nyaan’s Library)

\(i\) 辺の \(G\) の部分森」の通常型母関数を \(f(u)\) とおきます。この問題は \(f(u)\) を高速に計算できれば解くことができます。

\(g_S\)\(S \subseteq V\) を頂点集合とする木の個数とします。(公式解説の \(f(S)\) ) また、集合冪級数 \(G(X)\)\(g_S\) を用いて次のように定めます。

\[G(X) = \sum_{\emptyset \neq S \subseteq V} g_S X^S\]

すると、\(G(X)\)\(f(u)\) の間には次の関係が成り立ちます。

\[f(u) = [X^V] \sum_{1 \leq t} u^{N-t} \frac{G(X)^t}{t!}\]

よって、「\(g_S\) の列挙」および「 \(g_S\) が分かっているときの \(f(u)\) の計算」ができればこの問題を解くことができます。(ここまでは公式解説と本質的に同じです。)

まず、\(g_S\) の列挙は実はダブリングを用いた DP (集合冪級数のニュートン法とも解釈できる) で \(\mathrm{O}(2^N N^2)\) で列挙できます。
方法は次の通りです。\(S\) から頂点を \(1\) つ選んで \(n\) とします。\(n\) を削除して残った \(S\) の頂点の各連結成分を考えると、1 つの連結成分の寄与は (連結成分の通り数) \(\times\) (連結成分と \(n\) の間の辺の本数) になるので、\(S \in V \setminus n\) の場合をすべて計算した後に \(3^n\) DP で \(S \cap \lbrace n\rbrace\) の場合を計算して DP テーブルを倍にする、という操作を繰り返していく形の DP を立式できます。そしてこの DP はよく見ると subset exp なので \(\mathrm{O}(2^N N^2)\) に高速化できます。( 参考:Elegia 氏の論文 )

次に \(f(u)\) を計算します。これは \(G, G^2, \dots, G^N\)\([X^V]\) の係数を高速に求められればよいです。愚直に subset conv すると \(\mathrm{O}(2^N N^3)\) ですが、さらに高速化できます。
欲しいのは \([X^V]\) なので、 \(G\) を subset zeta した各点 \(\hat{G}_V(x)\) について \(\lbrack x^N \rbrack \hat{G}_V, \lbrack x^N \rbrack \hat{G}_V^2, \dots, \lbrack x^N \rbrack \hat{G}_V^N\) を計算して適宜寄与を足し合わせればよいです。これは長さ \(N\) の列同士の畳み込みを \(\mathrm{O}(N \log N)\) とすると \(\mathrm{O}(N^2 \log N)\) で計算出来るので、全体の計算量は \(\mathrm{O}(2^N N^2 \log N)\) に落ちます。
さらによくよく考えると、\(\hat{G}_V^1,\hat{G}_V^2,\dots,\hat{G}_V^{\lceil \sqrt{N} \rceil}\) および \(\hat{G}_V^{2 \lceil \sqrt{N} \rceil},\hat{G}_V^{3 \lceil \sqrt{N} \rceil},\dots,\hat{G}_V^{\lceil \sqrt{N} \rceil^2}\) を前計算すれば、求めていない項は前計算したいずれか 2 つの関数の積の \(N\) 次の係数になるため \(\mathrm{O}(N)\) で復元できるので、畳み込みの回数を \(\mathrm{O}(\sqrt{N})\) 回に落とせて \(\mathrm{O}(N^{1.5} \log N + N^2)\) で求めたいものを得られます。

よって全体の計算量は \(\mathrm{O}(2^N N^2)\) になります。(実用上は長さ \(N\) の列同士を \(\mathrm{O}(2^N \sqrt{N})\) 回愚直に畳み込む \(\mathrm{O}(2^N N^{2.5})\) 解法の方が高速に動作しそうです。)

\(\mathrm{O}(2^N N^{2.5})\) の実装例, 38 ms

おまけ

Tutte 多項式を \(T_G (x,y)\) と表すと、\(f(u)\) は次の式で表せます。(これを利用してより高速に解けないか考えましたが自分の知識では無理でした)

\[f(u) = u^{N-1} T_G \left(1 + \frac{1}{u}, 1 \right)\]

posted:
last update: