自动搬运

查看原文

来自洛谷，原作者为

	BJpers2 **

搬运于2025-08-24 21:53:11，当前版本为作者最后更新于2018-10-19 17:32:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

对于这道题目，很多题解都没有阐明第二问状态转移方程

$$f[i][j]=\sum_{k=1}^{i-1} \frac{f[k][j-1]+f[i-k][j-1]-f[k][j-1] \times f[i-k][j-1]}{i-1} $$

的正确性，其中$f[i][j]$表示在有$i$个叶子的随机树中，树的深度大于等于$j$的概率。他们几乎都没有讲清楚$/(i-1)$的来历。

显然，对于某一棵随机的，左儿子有$k$个叶子，右儿子有$i-k$个叶子的树，它的深度不小于$j$的概率为

$$P_k=f[k][j-1]+f[i-k][j-1]-f[k][j-1] \times f[i-k][j-1] $$

设操作$i-1$次，生成一棵的左儿子恰有$k$个叶子，右儿子有$i-k$个叶子的树的概率为$P'_k$

又因为在有$i$个叶子的随机树中，树的深度大于等于$j$的概率$P=\sum_{k=1}^{i-1} P_kP_k'$。

所以我们要证明$P_1'=P_2'=...=P_k'=...=P_{i-1}'=\frac{1}{i-1} (1)$

考虑一棵左儿子有$k$个叶子，右儿子有$i-k$个叶子的树是怎样生成的。如果把所有操作写成一个序列，$L$表示在左子树操作,$R$表示在右子树操作。由于最开始一定是根分裂，于是左右子树分别还有$k-1$,$i-k-1$个叶子需要生成。那最后看起来可能会是这样。

$$\underbrace{LRLLR....RLRLL}_{(k-1)*L,(i-k-1)*R}$$

它是一个有$k$个$L$和$i-k$个$R$的序列，也就是说，对于任何一对左右的操作序列，他们能组成$C_{i-k-1+k-1}^{k-1}=\frac{(i-2)!}{(k-1)!(i-k-1)!}$种不同的操作序列。

考虑生成一棵有$k$个叶子的树的方案数，也即有多少种操作序列。首先由$1$到$2$个叶子时只有一个选择，然后由$2$到$3$有两个选择......由$k-1$到$k$有$k-1$种选择。所以有$(k-1)!$种方案。

同理，生成一棵有$i-k$个叶子的树的方案数为$(i-k-1)!$

也即左子树可能的操作序列有$(k-1)!$种，右子树有$(i-k-1)!$种。

于是，将两条序列配对，共有$(k-1)!(i-k-1)!$种方案。

然后再乘上它们两条序列“揉在一起”的方案数(就是上面那个组合数)，就能得到生成一棵左儿子有$k$个叶子，右儿子有$i-k$个叶子的的树的方案数，它等于$(i-2)!$看起来与$k$无关。

这也就意味着，假如让我构造一颗有$100$个叶子的树，我左边放$99$个叶子,右边放$1$个叶子,跟我两边放五十个叶子的方案数竟然是一样的。也即等式$(1)$成立。

有了这个结论，我们才敢在转移时给每个概率除以$(i-1)$.