圣诞树题解

▶

INFO 题面

圣诞节到了，小 P 很孤独。

他只有一棵光秃秃的圣诞树，所以他决定玩玩它。不幸的是，这棵树被玩坏了，所以小 P 想将它复原。

小 P 的圣诞树是一棵 个节点的树，每个点是一个小球，第 个球上面有 个孔，孔之间是有区别的。小 P 需要用 条绳子将这些点连成一棵树。每个绳子应该连接两个不同的点的两个孔，且每个孔里最多有 根绳子。小 P 想知道，他能够复原出多少种不同的树。由于这个数太大了，他只想知道答案模 的结果。注意 不一定为质数。

定义两棵树相同当且仅当对于每一条边，它插入的两个孔在两棵树中相同。

模拟赛看到这题，想到之前看到过对树计数可以考虑使用 prufer 序列就学了一下，顺便练习了下推式子。

大力推式子

对树计数考虑使用 prufer 序列。方法类似OI-wiki 上的这个例子。

考虑枚举每个点的度数 。首先有 。最后 prufer 序列长度为 ，根据 prufer 序列的性质，每个点都出现了 次。

因此总共个 prufer 序列个数是

此时每个点有 种方案选择洞。

因此一个 序列对应的方案数为

大力推式子。

做一个变量代换 。

考虑从右边的 里每个提出来一个

此时把 移动到右边的分母上。

然后右边就变成组合数了。

此时外层还需枚举度数，最后的答案就是 此时考虑右边这个东西的组合意义：

相当于这个东西：

两个都在求有 类元素，第 类有 个，从中选择 个的方案数。上面那个式子是枚举每类选几个组合数乘起来，下面就是直接求。

因此答案就是

把 和后面的组合树和起来变成排列数。

然后就结束了。

组合意义

我们依旧考虑 prufer 序列。

将每个球的洞编号 到 。对于每个合法的树，考虑构造其 prufer 序列。

令点 被删除的时候，最后剩下的一条边插入 的洞的编号为 。容易发现序列 的个数为 。

考虑构造到 prufer 序列的第 项删除的边，假设第 项为 ，这条边插入到 的洞 。

此时还剩下 个点没有被选择。因此序列 的个数是 。

容易发现可以根据序列 构造出 prufer 序列（只需要将 对应的球的编号依次加入即可），根据 prufer 序列，序列 可以还原回原来的树。

因此合法的树的个数和序列 的个数是一样的。加乘原理乘一下即可。式子就是上面的式子。