Prufer序列泛做

Prufer数列是无根树的一种数列,常用来求解树的计数问题。

$Preface$

嗯,最近学了学一个叫做Prufer序列的东西,然后主要是跟树的计数有关。

基本概念与基本操作

首先下定义:Prufer序列是一个长度为$n-2$的序列。

我们考虑给定一棵带标号的无根树,找出编号最小的叶子节点,写下与它相邻的节点的编号,然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止。由于节点数$n>2$的树总存在叶子节点,因此一棵$n$个节点的无根树唯一地对应了一个长度为$n-2$的数列,数列中的每个数都在$1$到$n$的范围内。而这就是这棵树的$\boldsymbol{Prufer}$序列

为什么是$n-2$?

我们观察一棵树,$n-1$条无向边决定了总度数为$2n-2$,同时由于每个节点当自己是被删成叶子的时候不会被算进去,所以每个节点需要减去一的贡献,换句话说就是$Prufer$序列的长度为$n-2$。

emmm然后一个比较平凡的结论就是$\boldsymbol{P rufer}$序列中某个编号出现的次数就等于这个编号的节点在无根树中的度数-1。

同时我们接下来要不加证明地断言任何一个长为$n-2$、取值范围在$1$到$n$之间的数列都唯一地对应了一棵$n$个节点的无根树.

严格证明大家可以去Mt67的博客上翻(

想要更好的意会以上内容,需要我们考虑如何实现Prufer的呈现与复原:(摘自ProJ7-Jeffy的博客)

(1)无根树转化为 $Prufer$ 序列。
首先定义无根树中度数为1的节点是叶子节点。
找到编号最小的叶子并删除,序列中添加与之相连的节点编号,重复执行直到只剩下2个节点。
如下图的树对应的 $Prufer$ 序列就是 3,5,1,3

具体实现可以用一个 set 搞定,维护度数为 1 的节点。复杂度 $O(n\log n)$。
(2)$Prufer$序列转化为无根树。
设点集 V={1,2,3,...,n},每次取出 $Prufer$ 序列中最前面的元素$u$,在V中找到编号最小的没有在 $Prufer$ 序列中出现的元素$v$,给 $u,v$ 连边然后分别删除,最后在 V 中剩下两个节点,给它们连边。最终得到的就是无根树。
具体实现也可以用一个 set,维护 $Prufer$ 序列中没有出现的编号。复杂度 $O(n\log n)$。

扩展

  • $n$个点有标号无根树共有$n^{n-2}$种。

    • $\rm{Proof}:$ 仔细想想…似乎Prufer序列一共$n-2$项,于是就乘法原理就好了……
  • 接上一个,有根树的话因为对于每种方案里面的$n$个点都可以当作根,所以总数量是$n^{n-2}\cdot n=n^{n-1}$。

  • 假设每个点的度数已经确定了,设第$i$号点的度数为$d_i$,则显然有$\sum_{i=1}^{n}(d_i - 1)=n-2$,那么对于每个节点度数确定的带标号无根树数量就是
    $$
    \frac{(n-2)!}{\prod_{i=1}^n(d_i-1)}
    $$

    • $\rm{Proof}:$ 大概是一个排列组合的思想,我们可以认为是一共$n$种元素,选$n-2$个,每种元素有且必须有$d_i-1$个,求排列数。然后比较显然的是$(n-2)!$是总排列数,而每个元素一共有$d_i-1$个位置,对于同一种元素的同一种位置排布,我们多算了$A_{(d_i-1)}^{(d_i-1)}=(d_i-1)!$次的,所以分母上乘法原理起来去除这些贡献就好。
  • 接上一个, $n$ 个节点的度依次为 $d_1,d_2,…,d_{n-m}$,另外有 $m$ 个节点度数未知,求有多少种生成树?

    • 我们考虑首先计算一下$Prufer$序列该剩下多少未知项,设其数目为$\omega$,则$\omega=(n-2)-\sum_{d_i ~is~known} (d_i-1)$。那么本着瞎**去重的原则,我们考虑应该在分母上乘一个$\omega!$。而同时由于我们存在$m$个度数并未确定的点,在$Prufer$序列中占据了$\omega$个位置,所以我们分子上应该再乘上一个$m^{\omega}$。故总方案数就变成了:

$$
\frac{(n-2)!m^{\omega}}{\omega!\cdot \prod_{i=1}^{n-m}(d_i-1)}
$$

$A$ [HNOI2008]明明的烦恼

bzoj1005

其实就是上面扩展里面的一个推论,然后我们就用python水过去就好了233

然而BZOJ的Py只会一直Pending,所以还是什么时候再写一发高精度吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N = input()
Fac = [1]
for i in range(1, N - 1) :
Fac = Fac + [Fac[i - 1] * i]
Ans = Fac[N - 2]
cnt = 0
Sum = N - 2
for i in range(0, N) :
di = input()
if di == -1 :
cnt = cnt + 1
else :
Ans = Ans / Fac[di - 1]
Sum = Sum - (di - 1)
Ans = Ans / Fac[Sum]
for i in range(0, Sum) :
Ans = Ans * cnt
print (Ans)

$B$ 小猴打架

由于在BZOJ上是权限题,所以不得已去Luogu做…国内最大的盗版题市场

Luogu4430

我们发现这个题的Aim在于让我们求无根树有多少种不同的生成方式,比普通的Prufer序列多一个加边的顺序——毕竟Prufer只能处理树的形态不同&标号不同,所以我们理所当然地乘上一个$(n-1)!$。

1
2
3
4
5
6
int main(){//用sb代码来填补博文太短的空白
cin >> N ; Frac[0] = 1 ;
for (i = 2 ; i < N ; ++ i) (Ans *= N) %= Mod ;
for (i = 1 ; i < N ; ++ i) Frac[i] = Frac[i - 1] * i % Mod ;
(Ans *= Frac[N - 1]) %= Mod, cout << Ans << endl ; return 0 ;
}