生成函数，多项式

首先考虑这个题最显然的\(dp\)方程，设\(f(n)\)为根节点权值为\(n\)的二叉树个数，\(g(n)\)为权值为\(n\)的点是否存在

当\(n=0\)，\(f(n)=1\)

当\(n\neq 0\)

\[ f(n)=\sum_{i=1}^{n}g(n)\sum_{j=1}^{n-i}f(j)f(n-j-i) \]

然后设生成函数

\[ F(x)=\sum_{i=0}^{+\infty}f(n)x^i\\ G(x)=\sum_{i=0}^{+\infty}g(n)x^i\\ \]

可以得到

\[ F(x)=F^2(x)G(x)+1 \]

最后得到

\[ F(x)=\frac{2}{1+\sqrt{1-4G(x)}} \]

多项式开根+多项式求逆就好了

bzoj太卡了，没卡过，但是CF上AC了

代码：

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;void read(int &x) {    char ch; bool ok;    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;}#define rg registerconst int maxn=8e5+10,mod=998244353,g=3,gi=332748118;char ch[maxn];int n,m,tot,k,now=1,r[maxn],t[maxn],a[maxn],b[maxn],w[maxn],h[maxn],d[maxn],c[maxn],f[maxn],s[maxn];int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;}int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}int del(int x,int y){return x-y<0?x-y+mod:x-y;}int mi(int a,int b){    int ans=1;    while(b){        if(b&1)ans=mul(ans,a);        b>>=1,a=mul(a,a);    }    return ans;}void ntt(int *a,int n,int f){    for(rg int i=0;i
        
         i)swap(a[i],a[r[i]]);    for(rg int i=1;i
         
          <<=1){ int wn=mi(f?g:gi,(mod-1)/(i<<1)); for(rg int j=0;j
          
           <<1){ int w=1; for(rg int k=0;k
           
            >1);int m,len=0;for(m=1;m<=n<<1;m<<=1)len++; for(rg int i=0;i
            
             >1]>>1)|((i&1)<<(len-1)); for(rg int i=0;i
             
              >1]>>1)|((i&1)<<(len-1)); ntt(h,m,1),ntt(w,m,1); for(rg int i=0;i
              
               >1),get_ln(b,s,n); int m,len=0;for(m=1;m<=n<<1;m<<=1)len++; for(rg int i=0;i
               
                >1]>>1)|((i&1)<<(len-1)); for(rg int i=0;i