公式解説（https://atcoder.jp/contests/agc062/editorial/6391 ）の [2] までを前提とします．

葉の個数 \(i\) を \(x^i\) で表して母関数を作ることを考えます．

「根の片側につけるもの」の母関数を \(F\) として，根付き木の母関数は \(F^2\) です．

\(F\) の左側に長さ \(d\) のパスをつけることを考えると，\(f\) は次の関係式を持つことが分かります：

\(F = x(2! + 3!F + 4!F^2 + \cdots)\)

これは，\(G(x) = x\cdot \biggl(\sum_{d=0}^{\infty} (d+2)!x^d\biggr)^{-1}\) を用いて \(G(F(x)) = x\) という逆関数の形で書けます．これをラグランジュ反転すれば \([x^n]F^2\) を求めることができます．

答は解説にあるように，形式的べき級数の pow の係数 \([x^{2n-2}] G^n\) として表せます．

母関数にさらに「\(R_i=L_i+1\) となる \(i\) の個数」\(j\) という情報を \(y^j\) として付加して，\(2\) 変数母関数を考えます．

左側に伸ばすパスの先端の葉が \(R_i=L_i+1\) を満たすかで場合分けすれば，

\(F = xy (1! + 2!F + \cdots) + x((2!-1!) + (3!-2!)F + (4!-3!)F^2 + \cdots)\)

の形になります．\(y\) の多項式を係数とする形式的べき級数と見てラグランジュ反転により \([x^n]\) を求めることを考えると，求めるものは　\(x\) の形式的べき級数 \(G_0, G_1\) を用いて \([x^{2n-2}]\bigl(G_0(x)+G_1(x)y\bigr)^n\) の形になります．これの \([y^k]\) をとればよいので，結局計算するべきものは \(\binom{n}{k}[x^{2n-2}] G_0(x)^{n-k}G_1(x)^k\) の形になり，公式解説と同じ式が得られます．