Prufer 序列 学习笔记

Prufer 序列是一种将带标号的树用一个唯一的整数序列表示的方法。
在本文中，我们要求树的节点数 $\ge 2$。

Prufer 序列

Prufer 序列可以将一个带标号 $n$ 个节点的树用 $[1,n]$ 中的 $n-2$ 个整数表示，即 $n$ 个点的完全图的生成树与长度为 $n-2$ 值域为 $[1,n]$ 的数列构成的双射。

Prufer 序列可以方便的解决一类树相关的计数问题，比如凯莱定理：$n$ 个点的完全图的生成树有 $n^{n-2}$ 个。

对树构造 Prufer 序列

Prufer 是这样构造的：

每次选择一个编号最小的叶节点并删掉它，然后在序列中记录下它连接到的那个节点。

重复 $n-2$ 次后就只剩下两个节点，算法结束。

$\mathcal O(n \log n)$

显然，使用堆可以做到 $O(n\log n)$ 的复杂度。

$\mathcal O(n)$

使用一个指针代替堆找最小值，可以做到 $\mathcal O(n)$ 的复杂度。

具体而言，指针指向编号最小的叶节点。每次删掉它之后，如果产生了新的叶节点且编号比指针指向的更小，则直接继续删掉，否则自增找到下一个编号最小的叶节点。

Prufer 序列的性质

从上述构造 Prufer 序列的过程可以看出 Prufer 序列具有以下两个性质：

1. 在构造完 Prufer 序列后原树中会剩下两个节点，其中一个一定是编号最大的点 $n$。
2. 每个节点在序列中出现的次数是其度数减 $1$，因此没有出现的就是叶节点。

用 Prufer 序列构造树

根据 Prufer 序列的性质，我们可以得到原树上每个点的度数。

每次我们选择一个编号最小的度数为 $1$ 的节点，与当前枚举到的 Prufer 序列的点连接，然后同时减掉两个点的度数。重复 $n-2$ 次后就只剩下两个度数为 $1$ 的节点，其中一个是 $n$，把它们连接起来即可。

$\mathcal O(n \log n)$

同样地，显然，使用堆可以做到 $O(n\log n)$ 的复杂度。

$\mathcal O(n)$

类似地，使用一个指针代替堆找最小值，可以做到 $\mathcal O(n)$ 的复杂度。

具体而言，指针指向编号最小的度数为 $1$ 的节点。每次将它与当前枚举到的 Prufer 序列的点连接之后，如果产生了新的度数为 $1$ 的节点且编号比指针指向的更小，则直接继续将它与下一个 Prufer 序列的点连接，否则自增找到下一个编号最小的度数为 $1$ 的节点。

【模板】P6086 【模板】Prufer 序列

const int N = 5e6 + 7;
int n, o, f[N], p[N], d[N];
ll ans;

inline void TP() {
	for (int i = 1; i < n; i++) rd(f[i]), ++d[f[i]];
	for (int i = 1, j = 1; i <= n - 2; i++, j++) {
		while (d[j]) ++j; p[i] = f[j];
		while (i <= n - 2 && !--d[p[i]] && p[i] < j) p[i+1] = f[p[i]], ++i;
	}
	for (int i = 1; i <= n - 2; i++) ans ^= 1ll * i * p[i];
}

inline void PT() {
	for (int i = 1; i <= n - 2; i++) rd(p[i]), ++d[p[i]]; p[n-1] = n;
	for (int i = 1, j = 1; i < n; i++, j++) {
		while (d[j]) ++j; f[j] = p[i];
		while (i < n && !--d[p[i]] && p[i] < j) f[p[i]] = p[i+1], ++i;
	}
	for (int i = 1; i < n; i++) ans ^= 1ll * i * f[i];
}

int main() {
	rd(n), rd(o), o == 1 ? TP() : PT(), print(ans);
	return 0;
}

应用：图连通方案数

前面提到，Prufer 序列可以方便的解决一类树相关的计数问题。

考虑下面这个问题：

给定一个 $n$ 个点 $m$ 条边的带标号无向图，它有 $k$ 个连通块，求添加 $k-1$ 条边使得整个图连通的方案数。

设 $s_i$ 为第 $i$ 个连通块的点数，$d_i$ 为第 $i$ 个连通块的度数。

对于给定的 $d$ 序列构造 Prufer 序列的方案数为： $$\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}=\frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdots(d_k-1)!}$$

对于给定的 $d$ 序列使图连通的方案数为：

$$\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot \prod_{i=1}^k{s_i}^{d_i}$$

枚举 $d$ 序列使图连通的方案数为：

$$\sum_{d_i\ge 1,\sum_{i=1}^kd_i=2k-2}\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot \prod_{i=1}^k{s_i}^{d_i}$$

设 $e_i=d_i-1$：

$$\sum_{e_i\ge 0,\sum_{i=1}^ke_i=k-2}\binom{k-2}{e_1,e_2,\cdots,e_k}\cdot \prod_{i=1}^k{s_i}^{e_i+1}$$

考虑多元二项式定理：

$$(x_1 + \dots + x_m)^p = \sum_{c_i \ge 0,\sum_{i=1}^m c_i = p}\binom{p}{c_1, c_2, \cdots ,c_m} \cdot \prod_{i=1}^m{x_i}^{c_i}$$

原式变为：

$$(s_1+s_2+\cdots+s_k)^{k-2}\cdot \prod_{i=1}^ks_i$$

即：

$$n^{k-2}\cdot\prod_{i=1}^ks_i$$

【例题】CF156D Clues

const int N = 1e5 + 7;
int n, m, k, f[N], s[N];
modint ans = 1;

int get(int x) {
	return x == f[x] ? x : (f[x] = get(f[x]));
}

int main() {
	rd(n), rd(m), rd(P);
	if (P == 1) return print(0), 0;
	for (int i = 1; i <= n; i++) f[i] = i;
	for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), f[get(x)] = get(y);
	for (int i = 1; i <= n; i++) ++s[get(i)];
	for (int i = 1; i <= n; i++) if (i == get(i)) ++k, ans *= s[i];
	if (k == 1) return print(1), 0;
	print(ans *= (modint)n ^ (k - 2));
	return 0;
}

参考资料

• OI Wiki Prufer 序列

$\textstyle$