Prufer 序列学习笔记

一、前言

感觉它本身没有什么用。主要是用于计数问题。
前置知识：树的定义。

二、定义

对于一棵有 \(n\) 个节点的无根树 \(T\)，定义其 Prufer 序列为执行以下操作 \(n-2\) 次所形成的长度为 \(n-2\) 的正整数序列。
·选择其编号最小的度数为 \(1\) 的节点，输出唯一与其相邻的节点的编号。
·删除这个节点以及以其为端点的唯一边。
然后这个东西有一些性质：
1.容易知道最后树上一定是只留下 \(2\) 个度数为 \(1\) 的节点以及连着它们的边，其中一个编号为 \(n\)。证明：将无根树视作以 \(n\) 为根的有根树，容易知道由于树没有环，所以当点的个数 \(>1\) 时叶子结点的个数 \(\ge 2\)。如果树上节点个数 \(>1\)，存在一个叶子节点 \(y\ne n\)，删除节点 \(y\)，一定比删除节点 \(n\) 更优。□
2.这个东西可以与一棵有编号的无根树一一对应。
这个性质可以通过给出一种一一对应的映射方式来证明，见下文。
3.每个节点在 Prufer 序列里出现的次数是它在无根树上的度数减一，特别地，一开始的所有叶子节点不会出现在 Prufer 序列里。
证明：每往 Prufer 序列中加一个节点，就会删掉一条边。最后每个节点都至多只有一条边。我们知道因为每次删的都是叶子节点，所以每删去一个节点以及以其为端点的唯一边后，无根树仍连通。具体来说，如果我们将树视为以 \(n\) 为根的有根树，最后剩下的 \(2\) 个节点中一定有根 \(n\)，而且另外一个是 \(n\) 的一个子节点。而且容易知道一个节点 \(x\) 的所有子节点被删时，标在 Prufer 序列里的数都是 \(x\)，而一个节点 \(y\) 被删时，表在 Prufer 序列里的数是它的父亲节点的编号。那么除了 \(n\) 以外每个节点的子节点都被删光了，所以每个节点都被标了它的子节点的个数次，所以是 \(d_i-1\) 次。而对于节点 \(n\)，它的子节点个数是 \(d_i\)，它有一个儿子没被删，所以它也被标了 \(d_i-1\) 次。□

三、用途

1.可以知道有 \(n\) 个节点的不同有标号无根树一共有 \(n^{n-2}\) 棵，即有 \(n\) 个点的完全图的不同生成树一共有 \(n^{n-2}\)（Cayley 定理）。这是因为它的长为 \(n-2\) 的 Prufer 序列的每一位都可以填 \(1\) 到 \(n\) 的任意正整数。有 \(n\) 个节点的不同有标号有根树一共有 \(n^{n-1}\) 棵，因为处理出无根树之后，\(n\) 个点都可以做根。
2.可以知道有 \(n\) 个节点，其中编号为 \(i\) 的节点的度数为 \(d_i\)，并且满足 \(\sum\limits_{i=1}\limits^n{d_i}=2\times n-2\) 的不同有标号无根树有 \(\frac{(n-2)!}{\prod\limits_{i=1}\limits^n{(d_i-1)!}}\) 个。注意分母是先做阶乘再连乘。这是因为这棵无根树的 Prufer 序列可看作 \(d_1-1\) 个 \(1\)、\(d_2-1\) 个 \(2\)、……、\(d_n-1\) 个 \(n\) 所组成的，长度为 \(n-2\) 的可重复元素的全排列。
3.在造数据时，如果把树的每个节点的父亲节点标为一个随机的树，树的期望高度是 \(\sqrt n\)，而随机出 Prufer 序列再转换成树，树的期望高度是 \(\log n\) 的。

四、例题

例1.P6086 【模板】Prufer 序列

这一题是要实现 \(O(n)\) 的 Prufer 序列和有标号无根树的互相转换。
出于方便考虑，将无根树视作以 \(n\) 为根的有根树（事实上，根据定义，这不影响结果，而且只是为了在表述上更方便大家理解），于是下面将所有节点往 \(n\) 号节点方向非自身的最近点称为其父亲节点。

\(O(n\log n)\) 做法

首先实现父亲序列转 Prufer。一个明显的想法是记录所有点的子节点个数，维护一个小根堆（优先队列），把所有子节点个数为 \(0\) 的点扔进这个小根堆。然后每次取队头出队，然后删掉它，并且将它的父亲节点的度数减一，然后记录在 Prufer 序列里。接下来检查它父亲节点的子节点个数，如果降为 \(0\) 就入队。然后我们就求出了 Prufer 序列。时间复杂度 \(O(n\log n)\)，且常数较大。
然后就是 Prufer 序列转父亲序列，还是找出每一个节点的子节点数数（即在序列中出现的次数），然后找到所有子节点数为 \(0\) 的点，加入优先队列。每次取出队头，然后删掉它，并且我们可以知道第 \(i\) 次出队的点的父亲的编号实际上就是 Prufer 序列里第 \(i\) 个数，然后将其父亲节点的度数减一。最后就可以找到 \(n-2\) 个节点的父亲节点，然后 \(n\) 没有父亲节点，然后剩下一个节点的父亲节点为 \(n\)，然后我们就求出了父亲序列。时间复杂度 \(O(n\log n)\)，且常数较大。
所以就可以实现在 \(O(n\log n)\) 的时间内互相转换，同时也证明了 Prufer 序列与一棵有标号无根树一一对应。所以以上所说的所有计数问题成立。

int main(){
	n=read();m=read();
	if(m==1){
		for(int i=1;i<=n-1;i++)d[f[i]=read()]++;
		for(int i=1;i<=n;i++)if(!d[i])q.push(i);
		for(int i=1;i<=n-2;i++){
			p[i]=f[q.top()];q.pop();
			if(!--d[p[i]])q.push(p[i]);
		}
		for(int i=1;i<=n-2;i++)ans^=1ll*i*p[i];
	}else{
		for(int i=1;i<=n-2;i++)d[p[i]=read()]++;
		for(int i=1;i<=n-1;i++)f[i]=n;
		for(int i=1;i<=n;i++)if(!d[i])q.push(i);
		for(int i=1;i<=n-2;i++){
			f[q.top()]=p[i];q.pop();
			if(!--d[p[i]])q.push(p[i]);
		}
		for(int i=1;i<=n-1;i++)ans^=1ll*i*f[i];
	}
	cout<<ans<<'\n';
	return 0;
}

AC记录，通过了就很神奇，直接 \(n\log n\) 过 \(5000000\) 是吧。

\(O(n)\) 做法

但是这一题的正解是 \(O(n)\) 的。
我们可以发现，这一次删了一个点，那么下一次删哪个点。首先，有可能是原本就是度数为 \(1\) 的节点。其次，它还有可能是当前节点的父亲节点。
所以我们可以维护一个指针，初始时为 \(1\)，然后每次遇到一个节点 \(y\)，如果它的子节点被删光，那么就把它的父亲节点 \(x\) 记录进 Prufer 序列里，然后把 \(x\) 的残存的子节点数减一，如果 \(x\) 的子节点数因此变为 \(0\)，分类讨论：如果 \(x>y\)，则不用管它，继续自增指针；如果 \(x<y\)，那么要另外处理 \(x\)，删除它，继续记录 \(x\) 的父亲节点，然后继续判断……直到这个连锁反应停止为止。因为每个节点只会处理 \(1\) 次，所以时间复杂度 \(O(n)\)。
把 Prufer 序列转换成父亲序列同理。

int main(){
	n=read();m=read();
	if(m==1){
		for(int i=1;i<=n-1;i++)d[f[i]=read()]++;
		for(int i=1,j=1,x;i<=n-2;i++,j++){
			while(d[j])j++;p[i]=f[x=j];
			while(i<=n-2&&!--d[p[i]]&&p[i]<j)p[++i]=f[x=f[x]];
		}
		for(int i=1;i<=n-2;i++)ans^=1ll*i*p[i];
	}else{
		for(int i=1;i<=n-2;i++)d[p[i]=read()]++;p[n-1]=n;
		for(int i=1,j=1,x;i<=n-1;i++,j++){
			while(d[j])j++;f[x=j]=p[i];
			while(i<=n-1&&!--d[p[i]]&&p[i]<j)f[x=f[x]]=p[++i];
		}
		for(int i=1;i<=n-1;i++)ans^=1ll*i*f[i];
	}
	cout<<ans<<'\n';
	return 0;
}

AC记录
然后这个东西有什么用呢？基本没用，毕竟现有的大部分 OI 题只考计数，不考求 Prufer 序列。但是万一考了呢？学有余力的话还是学一学吧。

例2.P4981 父子

这一题就是求一个有 \(n\) 个点的完全图的生成树有几个。输出 $n^{n-2} $即可。

例3.P4430 小猴打架

这一题就是求一个有 \(n\) 个点的完全图的生成树的边共能形成多少种不同的排列。
注意到两棵不同的生成树至少有一个点不同，所以边形成的排列一定不同，所以答案就是生成树的棵数乘上树的边数的全排列的方法数，即 \(n^{n-2}\times (n-1)!\)。

例4.P2290 [HNOI2004]树的计数

使用上面（“用途”中）所讲的公式，可以知道是 \(\frac{(n-2)!}{\prod\limits_{i=1}\limits^n{(d_i-1)!}}\)。注意特判 \(\sum\limits_{i=1}\limits^n{d_i}\ne 2\times n-2\) 的情况（此时组不成一棵树，应该输出 0）以及图不连通的情况。

例5.P2624 [HNOI2008]明明的烦恼

考虑 Prufer 序列。令 \(s=\sum\limits_{d_i>0}^n{(d_i-1)}\)，\(k=\sum\limits_{d_i>0}^n{1}\)，\(q_i\) 代表第 \(i\) 个满足 \(d_r>0\) 的 \(r\)，那么我们知道 Prufer 序列里面有 \(s\) 个数是固定的，分别是 \(d_{q_i}-1\) 个 \(q_i\)，以及 Prufer 序列中剩下 \(n-2-s\) 个数，每一个数都可以是节点编号中的剩下 \(n-k\) 个数的任何一个。所以答案就是所有 \(d_{q_i}-1\) 个 \(q_i\) 的可重全排列乘上 \(n-2\) 个位置中选 \(s\) 个方案数乘上 \(n-k\) 的 \(n-2-s\) 次方，即 \(\frac{s!} {\prod\limits_{d_i>0}\limits^n{(d_i-1)!}}\times C_{n-2}^s\times (n-k)^{n-2-s}\)。要实现高精度乘除。