【转】Prufer codes与Generalized Cayley's Formula

Author： xzm2019
发布时间：February 18, 2019
3251views
No comments
1871字数
Categories：算法

最近补cf的[1113F][1]/[1109D][2]的时候要用到这个东西，但是找了半天也没找到什么，只看到一个别人也是这场比赛赛后写的这个学习笔记，给搬运一下。

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

## Prufer序列

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

1. 若当前树中只剩下两个点，退出，否则执行2。

2. 找到树中编号最小的节点，将与它相连的那个点的编号加入Prufer序列的末尾，并将这个叶子删除。返回1。

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

1. 令$A=\{1,2,\cdots,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,\cdots,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序列，每个点都恰出现度数-1次。于是根据乘法分配律，答案为(所有点权值之积)*(所有点权值之和)$^{n-2}$。

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

以上所有似乎都可以用Matrix Tree那一套理论通过化简行列式得到。
[1]: https://codeforces.com/contest/1113/problem/F
[2]: https://codeforces.com/contest/1109/problem/D

Last modification：February 28th, 2019 at 09:25 am

If you think my article is useful to you, please feel free to appreciate

Comment *

私密评论

Name *

Email *

Site

【转】Prufer codes与Generalized Cayley's Formula

xzm2019 • 2019 年 02 月 18 日

最近补cf的[1113F][1]/[1109D][2]的时候要用到这个东西，但是找了半天也没找到什么，只看到一个别人也是这场比赛赛后写的这个学习笔记，给搬运一下。

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

## Prufer序列

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

1. 若当前树中只剩下两个点，退出，否则执行2。

2. 找到树中编号最小的节点，将与它相连的那个点的编号加入Prufer序列的末尾，并将这个叶子删除。返回1。

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

1. 令$A=\{1,2,\cdots,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,\cdots,m$分别属于不同的树，的方案数。

先给出结论：$f(n,m)=m\cdot n^{n-m-1}$。

显然可以发现$f(n,1)=n^{n-2}$

证明：

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

应用：CF1109D

------

## 定理拓展

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

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

以上所有似乎都可以用Matrix Tree那一套理论通过化简行列式得到。
[1]: https://codeforces.com/contest/1113/problem/F
[2]: https://codeforces.com/contest/1109/problem/D

【转】Prufer codes与Generalized Cayley's Formula

Leave a Comment

2019南昌邀请赛网络赛个人记录（附官方题解）

北京理工大学第七届程序设计新生赛题解（unofficial）

第 43 届 ACM/ICPC 亚洲区域赛（南京）总结

北京理工大学第八届程序设计新生赛题解

Beijing Institute of Technology 2019.6 Monthly Contest 题解

欢迎使用来到xzm's blog

HQ Trivia UK 20180914 9pm BST 题目瞎扯

2019南昌邀请赛网络赛个人记录（附官方题解）

计算机组成原理学习笔记（Week1）

lintcode 384. 最长无重复字符的子串

【转】Prufer codes与Generalized Cayley's Formula