P3830 [SHOI2012] 随机树

P3830 [SHOI2012] 随机树

题目

题目描述

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

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

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

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

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

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

思路：

对于第一问，设 \(f_i\) 表示含有 \(i\) 个节点的二叉树的叶子的平均深度。

则每次会给所有叶子的深度和加上 \(f_{i-1}+2\) 。

则有 \(f_i=\frac{f_{i-1}\times (i-1)+f_{i-1}+2}{i}=f_{i-1}+\frac{2}{x}\)

对于第二问，考虑使用经典公式 \(E(x)=\sum_{i=0}^{+\infty} P(x \ge i)\) 。

设 \(f_{i,j}\) 表示有 \(i\) 个节点的二叉树，深度 \(\ge j\) 的概率。

考虑左子树有 \(k\) 个叶子，则右子树有 \(i-k\) 个叶子，则概率为 \(p\times(f_{k,j-1}+f_{i-k,j-1}-f_{k,j-1}\times f_{i-k,j-1})\) ，其中 \(p\) 为该情况出现的概率。考虑使用古典概型求 \(p\) 。

首先，左边有 \(k\) 个叶子，即 \(i-2\) 次选择中有 \(k-1\) 次选择了左儿子，其方案数为 \(\dbinom{i-2}{k-1}\) 。

然后，在左区间内生成 \(k\) 个叶子的二叉树方案数为 \((k-1)!\) ，同理，右子树为 \((i-k-1)!\) 。

则总方案数为 \(\frac{(i-2)!}{(k-1)!(i-k-1)!}\times (k-1)!(i-k-1)!=(i-2)!\) 。

又因为所有生成的总方案数为 \((i-1)!\) ，则概率 \(p=\frac{(i-2)!}{(i-1)!}=\frac{1}{i-1}\) 。