今天模拟赛被卡科技了，学一下这个东西，之前也看到很多次，只不过一直都没学。

算法简介

这是一种可以将带标号的树，转成唯一的整数序列表示的方法。而在“数树”题中也有大用。

算法流程大概是将带标号的 \(n\) 个节点的数用 \([1,n]\) 中的 \(n-2\) 个整数来表示一个树。

也可以理解成完全图的生成树和数列之间的双射。

算法流程

对树建立 \(prufer\) 序

具体什么是 \(prufer\) 序呢，就是每次将编号最小的叶节点取出来删掉，把他的父亲加入 \(prufer\) 序中，然后继续遍历下一个编号最小的叶节点。

所以我们显然用一个堆是能够很轻易的在 \(O(n\log n)\) 的时间复杂度中解决这个问题。

不过还有在线性时间中解决的算法。

1、考虑每次取出最小编号的叶节点，把他删掉。

2、令他父亲度数减一，判断他父亲度数是否为 \(0\) ，若为 \(0\) ，我们判断父亲节点是否编号小与当前节点，若小于，则一定父节点仍然是编号最小的父节点，那么我们就令父节点重复 \(1\) 操作。

这样为什么是对的呢，因为如果父节点小于当前节点编号，那么肯定是最小的，若不小于，那么在之后我们也可以枚举到。

因为每条边只会枚举一次，时间复杂度 \(O(n)\)

for(int i=1;i<n;++i) {
	scanf("%lld",&fa[i]);
	++deg[fa[i]];
}
for(int i=1;i<=n;++i) {
	int x=i;
	while(deg[x]==0) {
		pru[++tot]=fa[x];
		--deg[fa[x]];
		if(fa[x]>i) break;
		x=fa[x];
	}
}

对 \(prufer\) 序建立树

也和上面很类似，每次我们先找到编号最小的点，那么当前枚举到的 \(prufer\) 序，一定是这个点的父亲，那么我们就令这个点的父亲度数减一，同样判断一下是否小于当前节点，然后依次类推就可以了。

不过要注意，因为编号最大的节点不会被删掉，所以我们要令第 \(n-1\) 个位置的 \(prufer\) 序为 \(n\)

for(int i=1;i<=n-2;++i) {
	scanf("%lld",&pru[i]);
	++deg[pru[i]];
}
pru[n-1]=n;
int nw=0;
for(int i=1;i<=n;++i) {
	int x=i;
	while(deg[x]==0) {
		fa[x]=pru[++nw];
		--deg[fa[x]];
		if(fa[x]>i) break;
		x=fa[x];
	}
}

\(prufer\) 序的一些性质

• 一个点的度数是 \(d\) ，那么这个点在 \(prufer\) 序中出现次数为 \(d-1\)

• 构建 \(prufer\) 序过程中我们会删掉 \(n-2\) 个数，最终剩下两个数中一定有一个数是最大的数。

\(prufer\) 序最常用的还是在数树方面的应用。

• \(Cayley\) 定理：

大小为 \(n\) 的完全图，有 \(n^{n-2}\) 种不同的生成树。

至于证明是非常容易的，因为我们 \(prufer\) 序每个都对应唯一的一个无根树，然后我们序列长度是 \(n-2\) ，每个位置可以填 \([1,n]\) 所以我们就有 \(n^{n-2}\) 种不同的生成树。

不过更常用的还是下面这个定理：

看这个典题

给一个有 \(n\) 个点，\(m\) 条边，有 \(k\) 个连通块的带标号无向图，添加 \(k-1\) 条边使得图连通，求方案。

我们记 \(s_i\) 为第 \(i\) 个连通块的大小，那么答案就是：

\(n^{k-2}\prod\limits_{i=1}^k s_i\)

对于如何证明,太严谨的证明我不会，不过口糊一下我还是可以的。

我们可以将每个连通块看成一个点。

然后我们对于这些连通块要把它们连通，也就是看成点的情况下变成一棵树，所以我们就要构造一个长度为 \(k-2\) 的 \(prufer\) 序列，每个位置可以选择 \([1,n]\) 中的一个，我们相当于确定了连边中的父亲是谁，所以方案数为 \(n^{k-2}\)

现在我们还要确定每条连边中的儿子是谁，然后实际上因为每个连通块中只有一条连向父亲的边，而这条边中可以在自己连通块中任意选一个边，所以贡献是 \(s_i\)

所以最终答案就是 \(n^{k-2}\prod\limits_{i=1}^k s_i\)