prufer序列学习笔记

简介

$prufer$序列,是讲一棵树唯一转化为一个序列,在解决无根树的计数问题时十分有用。

无根树转$prufer$序列

我们定义一棵树的叶子为这棵树上度数为$1$的点。
每次找到编号最小的叶子节点,讲目前唯一与它相连的点的编号加入$prufer$序列,并删除这个叶子节点。
当最后还剩两个点的时候停止。
比如下图的$prufer$序列为$\{3,2,2,1,1\}$。
图1
实现的话拿个$set$维护一下叶子结点就好了。

$prufer$序列转无根树

先有一个点集V,表示目前可能为叶子的集合,初始时等于{1..n}。
从前往后扫$prufer$序列,设$prufer$序列上这一位为$u$,找到$V$中没在之后的$prufer$序列中出现过,编号最小的节点$v$,将$u,v$连上一条边,并把$v$从$V$中删除。
直至最后$V$中剩下两个节点,将这两个节点间连边后停止。
实现的话同样是一个set可以搞定。

性质

通过上面这两种转化方式,显然一棵无根树只会与恰好一个$prufer$序列对应.
最重要的性质就是每个点在$prufer$序列中恰好出现度数-1次。

带标号无根树计数

给你$n$个点,让你求出$n$个点的无根树的数量为多少。
BZOJ 1430
根据上面的两条性质,题目转化为在一个长度为$n-2$的序列中填上$[1..n]$的方案数,显然为$n^{n-2}$
例题中再乘以一个$(n-1)!$阶乘就好了。

带标号无根树计数推广

推广1

给你$n$个点,并给定每个点的度数$d_i$,求出这$n$个点可以构成无根树的数量。
题意可以转化为,在长度为$n-2$的数列中,填上$[1..n]$,且$i$出现$d_i-1$次。
那么答案应该为

推广2

给你$n$个点,$k$个点的度数确定,剩下点的度数随意,求出这$n$个点可以构成的无根树的数量。
BZOJ 1005
假设prufer序列还有$res$个位置未确定
$res=(n-2)-\sum\limits_{i=1}^{k}(d_i-1)$
总方案为

例题只需要在这个基础上加一个高精度即可。

带标号有根树计数

只需要给无根树选一个根就好了

结语

博主水平有限,目前只会不带标号的计数,带标号的有机会再更。