根付き木を数えて最後に適当な割り算をします．

\(n\) 頂点からなるラベル付き根付き木が good であるとは，「根に適当な長さのパスを付け加えると問題文の条件を満たす」こととします．

根付き木が good であるという条件の判定は，適当な tree dp で行えます．ある頂点での計算の際にはまずすべての subtree が good であるかを確認します．すべて good なときには，余っているパスを長さの和が適切になるようにマッチさせていき，残ったパスが \(1\) 個以下ならば true を返すという要領です．この計算手順にもとづいて数え上げの式を作りましょう．

\(L=2K+1\) とします． \(a_n\) を \(n\) 頂点の good なラベル付き根付き木の個数とします．\(1\leq k\leq L\) に対して，\(A_k\) を頂点数が \(\mod L\) で \(k\) と等しいようなラベル付き木の EGF とします（後の式が簡潔になるように，添字 \(1\leq k\leq L\) を用いました）．つまり：

\[A_k(x)=\sum_{i\equiv k\pmod{L}}\dfrac{a_i}{i!}x^i.\]

また次のように \(F, G\) を定めます．

\[F(x) = \sum_{n=0}^{\infty}\frac{x^n}{n!n!},\qquad G(x) = \sum_{n=0}^{\infty}\frac{x^n}{n!(n+1)!}\]

また \(H(x)=G(x)/F(x)\) とします．すると，次のような式が得られます：

• \(A_1 = x\exp(A_L) \prod_{1\leq i\leq K} F(A_iA_{L-i}).\)
• \(A_{k+1} = x\exp(A_L) A_k H(A_kA_{L-k}) \prod_{1\leq i\leq K} F(A_iA_{L-i}).\)

頂点数 \(i, L-i\pmod{L}\) の部分木が同数ずつあるという条件から \(F(A_iA_{L-i})\) という項が出てきて，頂点数 \(k\pmod{L}\) の部分木がひとつ余分にある場合に \(F(A_kA_{L-k})\) の代わりに \(A_kG(A_kA_{L-k})\) に置き換えるという立式です（基礎的な EGF の立式なので，これ以上詳しくは説明しません）．

左辺が \(A_{k+1}\), \(A_{L-k}\) であるような \(2\) つの式を比べることで，\(A_kA_{L-k}H(A_kA_{L-k})\) が \(k=1,2,\ldots,L-1\) について等しいという条件がでてきます．\(xH(x)\) は合成逆元を持つため，\(A_kA_{L-k}\) が \(k=1,\ldots,L-1\) で等しいことが分かります．

つまり，上の式で \(F\) や \(H\) に代入されるものはすべて等しいことが分かります．すると，\(A_1,\ldots,A_L\) はこの順に等比数列になることが分かります．

\(A(x) = A_1(x)\)，\(R(x) = A_2(x)/A_1(x)\) として，すべての条件が 2 つの形式的べき級数 \(A(x), R(x)\) に関する条件として書けることになります．これを実行すると次の 2 つの式が得られます：

• \(A = x\exp (AR^{L-1}) F(A^2R^{L-2})^K\)
• \(R = x \exp (AR^{L-1})F(A^2R^{L-2})^KH(A^2R^{L-2})\)

あとは上手く式変形をして合成や逆関数が使える形にします．いくつかの式変形の方針があると思います．以下私の計算の概略です．

\(A\), \(R\) にはそれぞれ \(xa(x^L), xr(x^L)\) と書けるので，\(a,r\) をあらためて \(A,R\) と書くことにして

• \(A = \exp (xAR^{L-1}) F(xA^2R^{L-2})^K\)
• \(R = \exp (xAR^{L-1})F(xA^2R^{L-2})^KH(xA^2R^{L-2})\)

という式があり，目標は \([x^N]A\) を求めることです．

• \(B=xA^2R^{L-2}\) とすると，\(AH(B)=R\) より \(xA^{L}H^{L-2}(B)=B\)，したがって \(xA^L = P(B)\) （ただし \(P(x)=x/H(x)^{L-2}\)）．

• \(P(B)=xA^L = x\exp (LxAR^{L-1}) F(B)^{KL}\) であるが，\(\exp\) の内側は \(P(B)=xA^L\) と \(B=A^2R^{L-2}\) の式にできる．ここから \(x = Q(B)\) というタイプの式を導出できて，\(Q\) の逆関数として \(B\) が，\(xA^L=P(B)\) などから \(A\) が計算できる．