首先考虑当节点数为n时，有多少个二叉树
设\(f[i]\)表示节点为i时二叉树的个数，有
\[f[n]=\sum_{i=1}^{n-1}f[i]f[n-1-i] \]注意这种递推式子也是卡特兰数的一种形式，所以为卡特兰数
其实手写出前四项为1,2,5,14我们就要有足够的敏感度知道这是卡特兰数
然后考虑叶子个数
我们假设我们已经画出了n个节点时所有的二叉树，那么不难发现，每一个二叉树可以再生成（n+1）张图
然后我们让所有的二叉树都生成（n+1）张图，我们只要把这些图中重复的去掉就好了
假设生成的一张图的叶子有d个，那么这张图肯定被重复生成了d次（每次都是在n个节点的所有二叉树的某一颗上添加一个叶子形成的），那么这张图的总贡献为\(d^{2}\)，但他本来应该只贡献\(d\)，所以我们要去重
我们只要让每一张生成的图的原始贡献从d变为1即可，这样直接累加就是d个1相加而不是d个d相加了，刚好与他应该的贡献相同
所以（n+1）个节点的叶子数之和就是（n+1）*\(cat_{n}\)，其中\(cat_{n}\)为卡特兰数，代表n个节点的二叉树数目，n+1就是这些二叉树中的每一所能生成的图的数量（每个图的贡献都为1了）
标签：贡献,洛谷,P3978,卡特兰,二叉树,概率论,生成,张图,节点 From： https://www.cnblogs.com/dingxingdi/p/17739108.html