P3978 [TJOI2015]概率论 题解

题目大意：求 $n$ 个点的有根二叉树的叶子结点的期望数。

0 前言（心路历程）可以跳过

一看题目，输入一个数，输出一个数，打表题！！！（喜得 30 分！！！）

之后将表中的小数化成分数，发现分母是卡特兰数，第 $i$ 个分子等于第 $i-1$ 个分母的 $i$ 倍，之后退出来一个式子 $\cdots \cdots$ （AC紫题！！！）

1 正文

如果用 $a_i$ 表示 $i$ 个结点的不同有根二叉树的个数，用 $b_i$ 表示 $i$ 个点的所有二叉树的叶子结点的和，那么答案显然就是 $\frac{b_n}{a_n}$ 。

2 求 $a_i$ 。

显然 $a_1=1$ 。

当 $i=2$ 时，添加了一个点，这个点可以

• 在 $1$ 的左子树中，有 $a_1$ 种方案；

• 在 $1$ 的右子树中，有 $a_1$ 种方案；

所以 $a_2=2=a_1+a_1$ 。

当 $i=3$ 时，添加了两个点，这两个点可以

• 在 $1$ 的左子树中，有 $a_2$ 种方案；

• 一个在 $1$ 的左子树中，一个在 $1$ 的右子树中，有 $a_1\times a_1$ 种方案；

• 在 $1$ 的右子树中，有 $a_2$ 种方案；

所以 $a_3=5=a_2+a_1\times a_1+a_2$ 。

当 $i=4$ 时，添加了三个点，这三个点可以

• 在 $1$ 的左子树中，有 $a_3$ 种方案；

• 两个在 $1$ 的左子树中，一个在 $1$ 的右子树中，有 $a_2\times a_1$ 种方案；

• 一个在 $1$ 的左子树中，两个在 $1$ 的右子树中，有 $a_1\times a_2$ 种方案；

• 在 $1$ 的右子树中，有 $a_3$ 种方案；

所以 $a_4=14=a_3+a_2\times a_1+a_1\times a_2+a_3$ 。

如果设 $a_0=1$，那么上面是个式子可以变成：

$a_1=a_0\times a_0$ 。

$a_2=a_0\times a_1+a_1\times a_0$ 。

$a_3=a_0\times a_2+a_1\times a_1+a_2\times a_0$ 。

$a_4=a_0\times a_3+a_2\times a_1+a_1\times a_2+a_3\times a_0$ 。

那么 $a_n=a_0\times a_{n-1}+a_1\times a_{n-2}+……+a_{n-1}\times a_0$ 。

这个数列就是经典的卡特兰数，通项公式为 $a_n=\frac{\left(2n\right)!}{n!\left(n+1\right)!}$ 。

3 求 $b_i$

part 1

一个 $i-1$ 个结点的数有 $i-2$ 条边，结点度数的和为 $2\left(i-2\right)$ 。

添加一个叶子之后原来 $i-1$ 个结点的度数和会加一。

而这$n-1$ 个结点，根结点度数最大为 $2$ ，其他结点的度数最大为 $3$ (一个父结点两个儿子结点），所以这 $i-1$ 个结点度数和最大为 $3\left(i-2\right)+2$ 。

度数和最大为 $3\left(i-2\right)+2$ ，当前度数为 $2\left(i-2\right)$ ，添加一个叶子度数加一，那么一个 $i-1$ 个结点的二叉树可以添加 $3\left(i-2\right)+2-2\left(i-2\right)=i$ 个叶子。

而 $i-1$ 个结点的二叉树有 $a_{i-1}$ 个，每个二叉树可以添加 $i$ 个叶子，所以总共可以添加 $a_{i-1}\times i$ 个叶子。

part 2

一个有 $i$ 个结点的二叉树，每删去一个叶子结点，就产生了一个 $i-1$ 个结点的二叉树，而因为 $i$ 个结点的二叉树总共有 $b_i$ 个结点，所以可以产生 $b_i$ 个 $i-1$ 个结点的二叉树。

part 1+2

会发现，将 $i-1$ 个结点的二叉树增加一个叶子形成 $i$ 个结点的二叉树，与将 $i$ 个结点的二叉树删去一个叶子形成一个 $i-1$ 个结点的二叉树是互逆（ 我语文不太好，反正是这个意思 ）的，所以 part 1 和 part 2 是互逆的，这样就得到了 $b_i=a_{i-1}\times i$ 。

4 求解

这样，我们得到了 $a_i$ 和 $b_i$ ，开始求解。

$$\frac{b_n}{a_n}=\frac{a_{n-1}\times n}{a_n}=\frac{\frac{\left(2n-2\right)!}{n!\left(n-1\right)!}\times n}{\frac{\left(2n\right)!}{n!\left(n+1\right)!}}=\frac{\frac{\left(2n-2\right)!}{\left(n-1\right)!}\times n}{\frac{\left(2n\right)!}{\left(n+1\right)!}}=\frac{\left(2n-2\right)!\left(n+1\right)!n}{\left(2n\right)!\left(n-1\right)!}=\frac{n^2\left(n+1\right)}{2n\times \left(2n-1\right)}=\frac{n\left(n+1\right)}{2\left(2n-1\right)}$$

5 代码

注意 $1$ ：题目要求误差不超过 $10^{-9}$ ，所以为了正确性，尽量输出至少九位小数。

注意 $2$ ：整数除整数结果是整数，所以 $n$ 开 double 或乘上 $1.0$ 。

注意 $3$ ：虽然 $n$ 是 int 范围内的，但是计算分母时会超出 int 范围，所以 $n$ 开 long long 或乘上 1ll 或 2ll

代码：

#include<cstdio>
#include<iostream>
int main()
{
	register int n;
	scanf("%d",&n);
	printf("%.9lf",1.0*n*(n+1)/(2ll*(2*n-1)));
	return 0;
}