Luogu P3978 [TJOI2015] 概率论

定义 \(f_i\) 为 \(i\) 个节点组成的二叉树数量，\(g_i\) 为 \(i\) 个节点组成的二叉树的叶子节点个数之和

设当前 \(i\) 个节点组成的二叉树有 \(a\) 个叶子，容易发现分别删掉其中的 \(1\) 个叶子节点就能得到一个对应的 \(i - 1\) 个节点的二叉树，总共会有 \(a\) 颗，可以发现每一个叶子节点对应的二叉树都为 \(g_i\) 产生了 \(1\) 的贡献

再设有 \(b\) 个节点有 \(1\) 个孩子，\(c\) 个节点有 \(2\) 个孩子，首先有个很显然的结论 \(a + b + c = i\) 不进行证明，其次能发现还有个结论 \(b + 2\times c = i - 1\)，证明考虑除了根节点其他节点都有父亲，\(b\) 代表着有 \(b\) 个儿子节点的 \(b\) 个父亲，\(c\) 代表 \(2\times c\) 个节点的 \(c\) 个父亲，所以和为除掉根节点的 \(i - 1\) 个节点

能发现对于这颗二叉树，要多一个叶子节点可以在 \(a\) 个节点的任意一个儿子下挂，\(b\) 个节点的剩余的那个儿子下挂，便有 \(2\times a + b\) 个位置可以挂，根据上述的 \(2\) 个结论可以推出对应数量 \(2\times a + b = 2\times (a + b + c) - (b + 2\times c) = 2\times i - (i - 1) = i + 1\)
所以可以知道每颗 \(i - 1\) 节点数的二叉树都可对 \(g_i\) 产生 \(i\) 的贡献，所以可得到 \(g_i = f_{i - 1}\times n\)

接下来考虑得到 \(f_i\)，考虑枚举左子树的节点个数 \(j\)，去掉根节点，右子树节点个数即为 \(i - j - 1\)，注意也可以有一个子树没有节点，所以可得到 \(f_i = \sum\limits_{j = 0}^{i - 1} f_j\times f_{i - j - 1}\)
然后发现这是个卡特兰数，所以 \(f_i = \frac{C_{2n}^{n}}{n + 1}\)

最后答案根据定义显然即为 \(\frac{g_{n}}{f_{n}}\)，当然是需要拆一下式子的
\(\frac{g_{n}}{f_{n}} = \frac{f_{n - 1}\times n}{f_{n}} = \frac{\frac{(2n - 2)!}{(n - 1)!\times (n - 1)!\times n}\times n}{\frac{(2n)!}{n!\times n!\times (n + 1)}} = \frac{(2n - 2)!\times n!\times n!\times n\times (n + 1)}{(2n)!\times (n - 1)!\times (n - 1)!\times n} = \frac{1\times n\times n\times 1\times (n + 1)}{(2n)\times (2n - 1)\times 1\times 1\times 1} = \frac{n\times (n + 1)}{2\times (2n - 1)}\)

// lhzawa(https://www.cnblogs.com/lhzawa/)
#include<bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    scanf("%lld", &n);
    long double ans = 1.0 * n * (n + 1) / 2 / (2 * n - 1);
    printf("%.9Lf\n", ans); 
    return 0;
}