补题需要用到的学习资料……从别人的博客里搬运一下。

原文链接:https://www.cnblogs.com/HocRiser/p/10390772.html
原文作者:HocRiser
原文发布时间:2019-02-17 12:55

Prufer Codes

在一棵 $n$ 个节点带标号树中,我们认为度数为 $1$ 的点为叶子。$n$个点的树的 Prufer 序列是经过下面流程得到的一个长度为 $n-2$ 的序列。

  1. 若当前树中只剩下两个点,退出,否则执行2。
  2. 找到树中编号最小的节点,将与它相连的那个点的编号加入 Prufer 序列的末尾,并将这个叶子删除。返回1。

显然,每棵树都唯一对应一个 Prufer 序列,而每个 Prufer 序列也唯一对应一棵树。可以通过一下流程得到这棵树。

  1. 令$A = \{1,2,\ldots,n\}$,不断重复 2 直到 Prufer 序列为空。
  2. 找到 $A$中最小的不在 Prufer 序列中的点,将其与 Prufer 序列首元素连边,然后同时删除这个点与序列首元素。
  3. 此时 $A$ 中还剩下两个点,将这两个点连边。

根据以上流程,不难发现:若点 $i$ 在树中的度数为 $a_i$,则它在 Prufer 序列中会出现 $a_i-1$ 次。

Cayley's Formula

Prufer 序列中的每个元素都可以从 $1$ 取到 $n$,且每种方案会唯一对应一棵带标号无根树。
所以,由于 Prufer 序列共有$n ^ {n-2}$ 个,$n$ 个点的带标号无根树就有$n ^ {n - 2}$ 种。

拓展:

  1. 显然,$n$ 个点的带标号有根树有 $n ^ {n - 2}$ 种。
  2. 当树中每个点的度数 $a_i$ 都已经确定后,由 Prufer 序列得,满足条件的树共有 $\frac{(n-2)!}{\prod a_i!}$ 种。

例题:BZOJ1005, BZOJ1211, BZOJ1430

Generalized Cayley's Formula

已知 $n,k$,求 $f(n,m)$ 表示 $n$ 个点组成的共有 $m$ 棵树的森林,且 $1,2,\ldots,m$ 分别属于不同的树,的方案数。

先给出结论:$f(n,m)=m\cdot n^{n-m-1}$
(显然可以发现$f(n,1)=n^{n-2}$)

证明:
显然,$f(1,1)=0$,$f(n,0)=0(n\geq 1)$。
数学归纳,假设对于所有 $i<n$ 的 $f(i,j)$都已证明。
考虑 $1$ 号点属于的那棵树,枚举 $1$ 号点的度数 $i$,则删除后这张图会变成 $n-1$ 个点,$m+i-1$ 棵树。
$f(n,m)=\sum\limits_{i=0}^{n-m}\binom{n-m}{i}f(n-1,m+i-1)$
将原式代入,有 $f(n,m)=\sum\limits_{i=0}^{n-m}\binom{n-m}{i}(m+i-1)(n-1)^{n-m-i-1}=mn^{n-m-1}$
命题得证。

拓展:显然 $n$ 个点组成有根树森林的方案为$\sum\limits_{k=1}^{n}n^{n-k-1}\times k\times \binom{n}{k}$

应用:CF1109D

定理拓展

$n$ 个带权的点,定义每条边的权值为相连的两个点的权值之积,定义一棵树的权值是所有边的权值之积,求所有树的权值和。

相当于每棵树中每个点的权值的度数次方的和。考虑 Prufer 序列,每个点都恰出现 $\text{度数} - 1$ 次。于是根据乘法分配律,答案为$(\text{所有点权值之积}) \times (\text{所有点权值之和}) ^ {n - 2}$。

这个推论包含了上面所有定理。当所有点权值取 $1$ 时,就是Cayley's Formula。当将点 $1 \sim m$ 缩成一个权值为 $m$ 的点时,就是Generalized Cayley's Formula。

以上所有似乎都可以用Matrix Tree那一套理论通过化简行列式得到。

最后修改:2019 年 02 月 24 日 10 : 04 AM
如果觉得我的文章对你有用,请随意赞赏