无语的智商题啊.居然没人写题解.

首先dp打个表.cnt[i]表示大小为i的二叉树的总个数.当然这个就是catlan数.然后son[i]表示大小为i的所有不同构的二叉树的叶子数的和.

然后经过找规律(翻oeis)发现son[i] = C(2n-2,n-1).

于是就没有于是了.推一下组合数发现answer=n2(n+1) / (n2) / (n*2-1).

代码好无语.