パスへの分解が可能な木の数え上げではなくパスへ分解する方法を数えることを考えます。もちろん 1 つの木に対してパスに分解する方法は複数あるので、答えを合わせるために個数に何らかの重みを付けて足し合わせることにします。

重み付けを考えるためにまずは木に対して何通りのパス分解があるかを考えてみます。
ある頂点 \(v\) に注目します。\(v\) から出る各辺 \(v \to w\) について、\(w\) 側で余る頂点数が一意に定まります。余る頂点数が \(x\) の辺と \(y\) の辺は \(x+y=2K+1\) の時にマッチできるので、頂点 \(v\) 周りにある余り \(x\) の辺の個数を \(C_{v,x}\) とおくと \(C_{v,2K+1-x} = C_{v,x}\) が必要で、この時マッチングの方法は \(C_{v,x}!\) 通りあることになります。
また、全ての \(v, 1 \leq x \leq K\) に対してマッチングの方法を決めればマッチングに従って \(N\) 本のパスを取ることが出来ることも確認できます。よって全ての \(v, 1 \leq x \leq K\) に対して重みを \(1 / C_{v,x}!\) 倍することが出来れば、パスの数え方で発生した重複を打ち消すことが出来ます。

しかし、それぞれの木に対して直接 \(1 / C_{v,x}!\) 倍して数えることは難しいので問題を変形します。
まず、\(2\) つのパス \(p, q\) が直接連結であるとは、\(2\) つのパスが端点以外の頂点で交わり、かつその点でパスを入れ替える (すなわち前述した辺同士のマッチングを入れ替える) ことが可能であることとします。 また、パスの集合 \(S\) が連結であるとは、全ての \(p, q \in S\) について \(S\) に含まれる直接連結な辺を辿ることで \(p\) から \(q\) に到達可能であることを意味します。
連結をこのように定義した上で、パスをいくつかのグループに分けることにします。各グループは連結である必要があります。また、直接連結な辺同士は必ずしも同じグループに属する必要はありません。

グループ分けの様子を \(1\) つの頂点周りについて観察してみます。頂点 \(v\) から見て \(x\) 余る辺の集合を \(X\)、\(2K+1-x\) 余る辺の集合を \(Y\) とします。\(X, Y\) をそれぞれパスのグループ分けに対応するように部分集合に分割すると \(X = X_1 \sqcup X_2 \sqcup \dots \sqcup X_s, Y = Y_1 \sqcup Y_2 \sqcup \dots \sqcup Y_s\) となったとします (ここで \(X_i\) と \(Y_i\) は同じグループに属しているとする。明らかに \(|X_i| = |Y_i|\) が成り立つ。)ここで各グループごとに \(W \lbrack |X_i| \rbrack\) の重みを掛けることを考えます。\(W\) の値を上手く設定することで木の重みを調整することにします。
パスへの分解を \(1\) つ固定して \(v\) 周りの余り \(x, 2K+1-x\) の辺を観察すると \(C_{v,x}\) 個のパスが \(v\) を通っています。さらにパスのグループ分けを行ったときに各グループごとに重み \(W \lbrack |X_i| \rbrack\) を掛けることにして、重みの総和が \(1 / C_{v,x}!\) になると上手くいきます。実際にこのような \(W\) は構成できて、閉じた式では書けませんが fps log を利用すれば計算できます。

この \(W\) を用いて求めたい答えを数えることを考えます。
ちょうど \(n\) 本のパスからなるグループをわたる重みの総和を \(A_n\) と置きます。そして問題を次の 2 ステップに分けることにします。

1. \(A_1, A_2, \dots, A_N\) を計算する
2. \(A_1, A_2, \dots, A_N\) から求めたい答えを計算する

1 番目のステップを考えます。
\(n\) 本のパスからなるグループは \(n(2K+1) + 1\) 頂点からなる木です。ここで、各頂点に \(0,1,\dots,2K+1\) のレベルを適切に割り振ることを考えます。隣接するレベルの間にのみ辺が張られており、また \(1\) つの木に対応するレベルの振り分け方は \(2\) 通りあります。
レベル \(0, 2K+1\) の頂点は葉なので一旦無視します。\(M = 2K\) とおきレベル \(1, 2, \dots, M\) の頂点にだけ注目します。頂点数は \(n(M-1) + 1\) です。すると、結局次の部分問題の答えの定数倍を求めればよいことになります。

部分問題

\(2\) 部グラフの全域木の重み付き数え上げを考える。 もともとある \(n(M-1)+1\) 頂点を \(L\) 側、\(n\) 本のパスに対応する \(n\) 頂点を \(R\) 側とする。辺 \((l, r)\) は頂点 \(l\) がパス \(r\) に含まれるという意味になる。

• \(R\) 側の頂点の次数は全て \(M\) であり、
• \(L\) 側の頂点の次数が \(i\) であれば重みに \(W \lbrack i \rbrack\) を掛ける

時の、条件を満たす全域木をわたる重みの総和は？

部分問題を解きます。右側頂点を根とする根付き木を考えます。木が真に部分木であるかどうか(すなわち親が存在するかどうか)によって答えが変わってくるので

• \(A(x)\) : 答えに関する母関数 (\(\frac{nA_n}{n! (n(M-1)+1)!}\) を係数に持つ母関数)
• \(B(x)\) : 親が存在する木に対する重みの総和に \(\frac{n}{n! (n(M-1)+1)!}\) を掛けた値の数列の母関数

とします。 この時、根のある子を取ってきた時にさらにその子が \(n\) 個あるような母関数は

\[U(x) = \sum_{n \leq 0} \frac{W_{n+1}}{n!}x^n \]

と表せます。よって

\[S(x) = \frac{U^M}{M!}, T(x) = \frac{U^{M-1}}{(M-1)!}\]

としたときに

\[ \begin{aligned} A(x) &= x S(B(x)) \\ B(x) &= x T(B(x)) \end{aligned} \]

という関係式が成り立ちます。よって \(B(x)\) の逆関数を求めて \(A(x)\) を関数合成により求める、という方法で \(A(x)\) を \(\mathrm{O}(N \log^2 N)\) で計算できます。(なお、少し式変形すると power projection 1 回で \(A(x)\) の係数を計算することができてこの部分を 2 倍高速化できます。)

• 逆関数・関数合成・power projection：Kinoshita (noshi91) と Li (Elegia) は 2024 年に関数合成および逆関数の計算を(次数を \(N\) として) \(\mathrm{O}(N \log^2 N)\) で計算するアルゴリズムを発見しました。Kinoshita と Li の論文や CodeForces での関連記事などは maspy さんの記事 に関連リンクがまとまっているのでそちらをご参照ください。

次に 2 番目のステップを考えます。
今、ちょうど \(n\) 本のパスからなるグループをわたる重みの総和 \(A_n\) が分かっています。ここで異なるグループ同士の干渉を考えなくてもよいため、グループのサイズの情報だけでマージの係数が計算できます。詳細な説明は省略しますが、\(F(x)\) を答えに \(\frac{n(2K+1)+1}{(n(2K+1)+1)!}\) を掛けた数列の母関数とすると

\[F(x) = \exp\left( \sum_{i=1}^\infty \frac{A_i}{((2K+1)i)!} x^i F(x)^{(2K+1)i}\right)\]

という式を得られます。この式のままニュートン法を用いて \(F(x)\) を計算することもできますが(ニュートン法内部で Kinoshita-Li 関数合成を行います)、少し変形すると関数 \(G(x)\) を用いて \(x F^{2K+1} = x G(x F^{2K+1})\) という式に変形できるため Kinoshita-Li 逆関数を用いて \(F\) を計算することができてその方が容易でしょう。

以上の内容を適切に実装すればこの問題を \(\mathrm{O}(NK + N \log^2 N)\) で解くことが出来て、十分高速です。