P3830 [SHOI2012] 随机树

题目背景

SHOI2012 D1T3

题目描述

一棵含 $n$ 个叶结点的二叉树可以通过如下方式生成。初始时只有根结点。首先，将根结点展开（本题中的“展开”是指给一个叶结点添上左、右两个子结点）：

[a]

然后，等概率地随机将两个叶结点中的一个展开，即生成以下两棵树之一：

[b]

之后，每次在当前二叉树的所有叶结点中，等概率地随机选择一个，将其展开。

不断地重复这一操作，直至产生 $n$ 个叶结点为止。例如，某棵含 5 个叶结点的二叉树可能按如下步骤生成。

[c]

对于按该方式随机生成的一棵含 $n$ 个叶结点的二叉树，求：

叶结点平均深度 的数学期望值。
树深度 的数学期望值。约定根结点的深度为 0。

输入格式

输入仅有一行，包含两个正整数 $q$ , $n$ ，分别表示问题编号以及叶结点的个数。

输出格式

输出仅有一行，包含一个实数 $d$ ，四舍五入精确到小数点后 $6$ 位。如果 $q = 1$ ，则 $d$ 表示叶结点平均深度的数学期望值；如果 $q = 2$ ，则 $d$ 表示树深度的数学期望值。

输入输出样例 #1

输入 #1

1 4

输出 #1

1	`2.166667`

输入输出样例 #2

输入 #2

2 4

输出 #2

1	`2.666667`

输入输出样例 #3

输入 #3

1 12

输出 #3

1	`4.206421`

输入输出样例 #4

输入 #4

2 12

输出 #4

1	`5.916614`

说明/提示

【样例 1、样例 2 说明】

数学期望值是随机变量的值乘以其概率的总和：记随机变量 $X$ 可能的取值为 $x_{1}, x_{2}, \dots, x_{n}$ ，它们取到的概率分别为 $p_{1}, p_{2}, \dots, p_{n}$ ，那么随机变量 $X$ 的数学期望值就是

E (X) = \sum_{i = 1}^{n} p_{i} x_{i}

例如，掷一枚写有 1、2、3、4、5、6 这 6 个数的均匀骰子，掷到的数的数学期望值是：

E = \frac{1}{6} \times 1 + \frac{1}{6} \times 2 + \frac{1}{6} \times 3 + \frac{1}{6} \times 4 + \frac{1}{6} \times 5 + \frac{1}{6} \times 6 = 3.5

尽管 3.5 不是骰子上的某个数。又如，一道 4 选 1 的选择题，答对得 5 分，不答不得分，答错倒扣 1 分。那么，当我们不答时，一定得 0 分；而等概率地随便猜一个时，得分的数学期望值是：

本题中，根据二叉树的生成方式，当 $n = 4$ 时，下图中前四棵树被生成的概率均为 $1 / 6$ ，最后一棵树被生成的概率为 $1 / 3$ 。它们的叶结点平均深度分别是 $9 / 4$ 、 $9 / 4$ 、 $9 / 4$ 、2，因此叶结点平均深度的数学期望值是

E = \frac{1}{6} \times \frac{9}{4} + \frac{1}{6} \times \frac{9}{4} + \frac{1}{6} \times \frac{9}{4} + \frac{1}{6} \times \frac{9}{4} + \frac{1}{3} \times 2 = \frac{13}{6}

而它们的树深度分别是 3、3、3、3、2，因此树深度的数学期望值是

E = \frac{1}{6} \times 3 + \frac{1}{6} \times 3 + \frac{1}{6} \times 3 + \frac{1}{6} \times 3 + \frac{1}{3} \times 2 = \frac{8}{3}

【数据规模】

测试数据编号	$q$	$n$
1,2	$q = 1$	$2 \leq n \leq 10$
3,4,5	$q = 1$	$2 \leq n \leq 100$
6,7	$q = 2$	$2 \leq n \leq 10$
8,9,10	$q = 2$	$2 \leq n \leq 100$

题解

显然 $n$ 个叶子节点的树是由根节点经过 $n - 1$ 次展开操作得到。

设 $f (k)$ 表示有 $k$ 个叶子节点的树的叶子节点平均深度。在一个有 $k - 1$ 个叶子节点的树中随机选择一个叶子节点展开，则树的叶子节点深度总和会增加 $f (k - 1) + 2$ 。因此有状态转移：

f (k) = \frac{f (k - 1) \times (k - 1) + f (k - 1) + 2}{k} = f (k - 1) + \frac{2}{k}

计算深度期望需要用到这个式子：

\begin{aligned} E (X) & =\sum_{i = 1}^{+ \infty}iP(X=i) \\ =\sum_{i = 1}^{+ \infty}\sum_{j = 1}^{i}P(X=i) \\ =\sum_{1 \leq j \leq i < + \infty}P(X=i) \\ =\sum_{j = 1}^{+ \infty}\sum_{i = j}^{+ \infty}P(X=i) \\ =\sum_{j = 1}^{+ \infty}P(X\geqj) \end{aligned}

我们设 $g (k, j)$ 表示有 $k$ 个叶子，树的深度 $X \geq j$ 的概率。

转移时枚举左右子树有多少个叶子：

g (k, j) = \sum_{i = 1}^{k - 1} \frac{1}{k - 1} (g (i, j - 1) + g (k - i, j - 1) - g (i, j - 1) \times g (k - i, j - 1))

式子含义：左右只要一边深度 $\geq j - 1$ 即可，因此需要减掉两边都 $\geq j - 1$ 的概率。

最后答案即为

E (X) = \sum_{i = 1}^{n - 1} P (X \geq i) = \sum_{i = 1}^{n - 1} g (n, i)