第一次自己做出来多项式计数题，纪念一下。
首先题目中这个性质可以归纳为对恰好有 n 个编号为 1 的点，而且所有叶子和根节点必须为 1，所有除了根以外标 1 的点到祖先第一个 1 距离 \leq 2 的无标号有根二叉树计数。
我们考虑一个 DP，设 f_{i} 为恰好有 i 个点标 1 且根节点标了 1 的合法树个数，g_i 为恰好有 i 个点标 1 且根节点标了 0 的合法树个数。
因为所有 1 到祖先 1 距离 \leq 2 所以不难得到标了 0 的点儿子必须都是 1，所以有 g_{i}=\sum\limits_{j+k=i}f_{j}\times f_k，而标了 1 的点没有限制，所以下面可以任意挂，则有 f_{i}=\sum\limits_{j+k=i-1}(f_{j}+g_j)\times(f_k+g_k)，发现两个式子都是卷积的形式，可以写出 f_i,g_i 的生成函数 F(x)=\sum\limits_{i\geq 0} f_ix^i,G(x)=\sum\limits_{i\geq 0} g_ix^i 从生成函数的角度考虑。
不过注意一下边界条件 f_0,g_0，观察样例的图知道 f_1=1,g_1=2 所以可以得到 f_0=1,g_0=0，所以上面两个 DP 转移可以写成 G=F^2-1,F=x(F+G)^2+1，代入一下就知道 F=x(F^2+F-1)^2+1。
然后有四次你实在不好解方程得到 F 的一个式子，不过你发现方程里面有个 x，这时你想到了复合逆。
于是整理一下变成 \frac{F-1}{(F^2+F-1)^2}=x，你知道 [x^0]F(x)=1，所以此时 F(x) 没有复合逆，但是你又不用求 [x^0]F(x) 的值所以可以换元，设 F_1=F-1，则 x=\frac{F_1}{((F_1+1)^2+F_1)^2}=\frac{F_1}{(F_1^2+2F_1+1)^2}，此时你显然可以构造 F_1 的复合逆 G(x)=\frac{x}{(x^2+3x+1)^2}。
然后大家都知道拉格朗日反演：[x^n]P(F(x))=\frac{1}{n}[x^{n-1}]P'(x)(\frac{x}{G(x)})^n，直接代入就知道：
[x^n]F_1(x)=\frac{1}{n}[x^{n-1}](x^2+3x+1)^{2n}
右边这个系数简直太好求了，直接二项式定理展开就行了。
\begin{aligned}
[x^n]F_1(x)&=\frac{1}{n}\sum\limits_{i\geq 0}\binom{2n}{i}[x^{n-1-2i}](3x+1)^{2n-i}\\
&= \frac{1}{n}\sum\limits_{i\geq 0}\binom{2n}{i}\binom{2n-i}{n-1-2i}3^{n-1-2i}
\end{aligned}
时间复杂度 O(n)，代码很简单不放了。
bouns：对 G(x) 求导找一下关系可以得到 (x^2+3x+1)G'(x)=2n(2x+3)G(x) 可以化得：m[x^m]G(x)=(6n-3m+3)[x^{m-1}]G(x)+(4n-m+2)[x^{m-2}]G(x)，这是整式递推的形式，直接递推也能 O(n) 而且常数小很多。
直接使用P6115 【模板】整式递推的科技可以做到 O(\sqrt n\log n)，但我不会。