题解 P3830 【[SHOI2012]随机树】

对于这道题目，很多题解都没有阐明第二问状态转移方程 $$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)$.