题解 P3978 【[TJOI2015]概率论】

Kubic · 2020-01-16 20:30:09 · 题解

声明：我是来为rqy神仙的题解的证明部分作补充的。

rqy神仙的思维太过跳跃，本蒟蒻看了好久才明白。

证明：g_n=f_{n-1}\times n

Part 1

对于每一个n个节点的二叉树，假设它有a个叶子节点，则分别删去这a个节点，就能得到a个n-1个节点的二叉树。也就是说，我们可以认为这一个n个节点的二叉树对应了k个n-1个节点的二叉树，每有一次对应就会对g_n产生1的贡献。我们的任务转变为求出共有多少次对应。

Part 2

对于每一个n个节点的二叉树，假设它有b个拥有恰好1个子节点的节点，c个拥有恰好2个子节点的节点。那么一个显然的结论是a+b+c=n。还有一个不那么显然的结论是b+2c=n-1。这是为什么呢？因为除了根节点之外，每一个节点都有恰好1个父节点，也就是说，所有点的子节点就会不重不漏地包含除了根节点之外的所有节点，总共就有n-1个节点。

Part 3

对于每一个n个节点的二叉树，当前的每一个叶子节点会提供2个悬挂新叶子节点的位置，当前的每一个拥有恰好1个子节点的节点会提供1个悬挂新叶子节点的位置，所以它总共有2a+b个可以悬挂新叶子节点的位置。根据Part 2中的2个结论，我们可以得出2a+b=n+1。也就是说，总共有n+1个位置可以悬挂新叶子节点。

因此，每一个n-1个节点的二叉树在计算g_n的贡献中都总共被对应了n次，也就是说，g_n就等于n-1个节点的二叉树总数\times n。于是我们可以得到g_n=f_{n-1}\times n。

其余部分可以参照rqy神仙的题解，这里不再赘述。

希望对大家有帮助！