Solution

考虑一个 $n$ 个点的二叉树如果有 $k$ 个叶子节点就有 $k$ 种拆法拆成一棵 $n-1$ 的树，而我们要求所有的树的 $k$ 之和。
发现其实 $k$ 之和就等价于任意一棵 $n-1$ 的树都有 $n$ 种添法添成 $n$ 的树。

即 $n$ 拆成 $n-1$ 的方案数之和等于 $n-1$ 添成 $n$ 的方案数之和。这种证法非常感性，但足够简单。更深一步的考虑，每种添法都有唯一对应的拆法，因此这个结论是正确的。

所以 $n$ 个点的二叉树的叶子节点数目之和等于 $n-1$ 个点的二叉树的方案数乘以 $n$。

然后发现 $n$ 个点的方案数就是卡特兰数，然后化下公式结论就有了。

Code

// Code by ajcxsu
// Problem: Etree

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    printf("%.9lf", (double)n*(n+1)/2/(2*n-1));
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3978.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆