• $\operatorname{prufer}$序列
  • 定义
  • 构造
    • 无根树到序列
    • 序列到无根树
  • 性质与相关结论

\(\operatorname{prufer}\)序列

定义

一种无根树上的数列。

由顶点标号的无根树转化而来。且对于一棵确定的无根树，其对应的\(\operatorname{prufer}\)序列也是唯一确定的。

构造

无根树到序列

有两个基本操作：

• 找到一个编号最小的叶节点，不妨记为\(x\)。
• 把与\(x\)相连的节点加入序列，然后把\(x\)从树中删除。

重复这两个操作，直到整棵树剩下2个节点。

容易知道，我们加入序列的数共有\(n-2\)个，这\(n-2\)个数构成的序列就是\(\operatorname{prufer}\)序列。

举个例子，对于下图这棵树：

对它执行上述操作：

• \(x=4,p=\{2\}\)
• \(x=5,p=\{2,3\}\)
• \(x=3,p=\{2,3,1\}\)
• \(x=6,p=\{2,3,1,2\}\)

那么对于这棵有6个节点的节点标号无根树，我们就得到了长度为4的\(\operatorname{prufer}\)序列\(\{2,3,1,2\}\)

代码实现：

inline void Tree_Prufer() {
	for (ri i=1;i<n;++i) f[i]=read(),++ind[f[i]];
	for (ri i=1,j=1;i<=n-2;++i,++j) {
		while (ind[j]) ++j;
		p[i]=f[j];
		while (i<=n-2 && !(--ind[p[i]]) && p[i]<j) p[i+1]=f[p[i]],++i;
	}
	for (ri i=1;i<=n-2;++i) ans^=(1ll*i*p[i]);
	printf("%lld",ans);
}

序列到无根树

三个基本操作：

• 取出序列最前面的元素，记为\(x\)。
• 取出在点集中且当前不在序列中的最小元素。
• 在\(x,y\)间连边。

显然最后点集中还会剩下2个点（ \(n-(n-2)=2\) ），把这两点连一条边。

基本就是上面的逆操作，代码如下：

inline void Prufer_Tree() {
	for (ri i=1;i<=n-2;++i) p[i]=read(),++ind[p[i]];
	p[n-1]=n;
	for (ri i=1,j=1;i<n;++i,++j) {
		while (ind[j]) ++j;
		f[j]=p[i];
		while (i<n && !(--ind[p[i]]) && p[i]<j) f[p[i]]=p[i+1],++i;
	}
	for (ri i=1;i<n;++i) ans^=(1ll*i*f[i]);
	printf("%lld",ans);
}

性质与相关结论

性质：\(\operatorname{prufer}\)序列与无根树唯一确定对应。

结论1：度数为\(d[i]\)的节点恰好会在\(\operatorname{prufer}\)序列中出现\(d[i]-1\)次。

简单证明：

先考虑最简单的情况，该节点度数为1，那么它会被直接删掉，也就是出现的次数为0；

将此思想拓展，若该节点度数 \(d[i]\) 大于1，那么它有边直接相连的节点（除了它的父亲）（这个节点数也就是它的度数）每被删掉一个，它就会在序列中出现一次。所以共出现 \(d[i]-1\) 次。

结论2：\(n\)个节点的完全图的生成树个数为\(n^{n-2}\)。

简单证明：

\(n\)个点的无根树对应的\(\operatorname{prufer}\)序列的长度为\(n-2\)，这\(n\)个原来的节点标号均可能在这\(n-2\)个位置上出现，也就是说，有\(n^{n-2}\)种可能的\(\operatorname{prufer}\)序列。每个\(\operatorname{prufer}\)序列都可以对应一棵生成树。

结论3：对于给定度数\(d[i]\)的无根树，它的\(\operatorname{prufer}\)序列有

种情况。

简单证明：

由结论1可得：

\(\Rightarrow\) 求\(d[i]-1\)个\(i\)的可重全排列个数。

*可重全排列：全排列个数 除以 重复元素内部全排列个数

例题待补。