题解 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).