IX.[TJOI2015]概率论
O E I S 大 法 好
我们设\(f(x)\)表示\(x\)个节点的二叉树的叶子节点个数之和，\(g(x)\)表示\(x\)个节点的二叉树总数。则答案就是\(\dfrac{f(n)}{g(n)}\)。
显然\(g\)就是卡特兰数；\(f\)通过\(O(n^4)\)暴力DP可以打出表来，发现是
1, 2, 6, 20, 70, 252, 924, 3432, 12870...
丢进OEIS一看，发现它就是\(\dbinom{2n-2}{n-1}\)。然后\(g\)的递推公式就是\(\dfrac{\binom{2n}{n}}{n+1}\)；两个一除，推推式子就得到了答案\(\dfrac{n(n+1)}{2(2n-1)}\)。
考虑它的实际意义——
一棵\(n\)个点的二叉树，假设它又长出了一片叶子，则这就对应了一棵\(n+1\)个节点的二叉树。显然这片叶子有\(2n-(n-1)=n+1\)种长法。
我们再来考虑一棵\(n+1\)个节点的二叉树。删去它的每个叶子，都会得到一棵\(n\)个点的二叉树。显然这两种情况是一一对应的。
故我们就有\((n+1)g(n)=f(n+1)\)。代入\(g\)的递推式，就能得到\(f\)。
代码（注释部分是\(O(n^4)\)的DP）：
#include<bits/stdc++.h>
using namespace std;
int n;
//int f[110][110],g[110],p[110];
int main(){
scanf("%d",&n);
printf("%.10Lf",(long double)(n+1)*n/2/(2*n-1));
// f[0][0]=f[1][1]=1;
// for(int i=2;i<=n;i++)for(int j=0;j<=i;j++)for(int k=0;k<i;k++)for(int l=0;l<=j;l++)f[i][j]+=f[k][l]*f[i-1-k][j-l];
// for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)p[i]+=f[i][j]*j;
// g[0]=1;
// for(int i=1;i<=n;i++)for(int j=0;j<i;j++)g[i]+=g[j]*g[i-j-1];
// for(int i=1;i<=n;i++)printf("(%lld/%lld)",p[i],g[i]);
return 0;
}