Prufer 序列

一个长度为 n−2n - 2，值域为 [1,n][1, n] 的序列可以表示一棵 nn 个节点的有标号无根树，这个序列就是 Prufer 序列。

对树构造 Prufer 序列

每次选择一个编号最小的叶节点并删掉它，然后在序列末尾加入它连接到的那个节点的编号。

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

Prufer 序列的性质

从上述构造 Prufer 序列的过程可以看出 Prufer 序列具有一个重要的性质：每个节点在序列中出现的次数是其度数减 11。

用 Prufer 序列构造树

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

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

模板题代码：

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
typedef long long ll;
using namespace std;

const int N = 5000001;
int n, _, fa[N], pf[N], d[N];
ll t2p(){
	for (int i = 1;i < n;i ++) scanf("%d", &fa[i]), d[fa[i]] ++;
	int p = 0, c = 0;ll res = 0;
	while (c < n - 2){p ++;
		while (d[p]) p ++;pf[++ c] = fa[p];
		while (c < n - 2 && !-- d[pf[c]] && pf[c] < p) pf[c + 1] = fa[pf[c]], c ++;
	}
	for (int i = 1;i <= n - 2;i ++) res ^= 1ll * i * pf[i];
	return res;
}
ll p2t(){
	for (int i = 1;i <= n - 2;i ++) scanf("%d", &pf[i]), d[pf[i]] ++;pf[n - 1] = n;
	int p = 0, c = 0;ll res = 0;
	while (c < n - 1){p ++;
		while (d[p]) p ++;fa[p] = pf[++ c];
		while (c < n - 1 && !-- d[pf[c]] && pf[c] < p) fa[pf[c]] = pf[c + 1], c ++;
	}
	for (int i = 1;i < n;i ++) res ^= 1ll * i * fa[i];
	return res;
}
int main(){
	scanf("%d%d", &n, &_);
	printf("%lld", _ == 1 ? t2p() : p2t());
}

Cayley 公式

我们发现两种转换方式都是唯一的，于是可以知道 nn 个节点的有标号无根树与长度为 n−2n - 2 值域为 [1,n][1, n] 的数列构成双射，于是，有 nn−2n^{n - 2} 棵不同的 nn 个节点的有标号无根树。

另外，我们给无根树定个根，一共有 nn 种可能的根，那么就有 nn−1n^{n - 1} 棵不同的 nn 个节点的有标号无根树。

[HNOI2004] 树的计数

看到关于度数的计数，考虑 Prufer 序列。

我们知道，一个节点在 Prufer 序列里出现的次数为它的度数 −1- 1，那么 11 出现的次数是 d1−1d_1 - 1，22 出现的次数是 d2−1d_2 - 1，……，nn 出现的次数是 dn−1d_n - 1，这样的序列一共有 (n−2d1−1,d2−1,…,dn−1)\dbinom{n - 2}{d_1 - 1, d_2 - 1, \dots, d_n - 1} 个。

Clues

首先把已有的边连起来，然后问题就转化成了：共有 nn 个点，已有的边已经连出了 mm 个连通块，第 ii 个连通块的大小为 aia_i，求用 m−1m - 1 条边将它们连接起来的方案数。

设第 ii 个联通块的点在 Prufer 序列里出现了 xix_i 次，答案为：

∑∑xi=m−2(m−2x1,x2,…,xn)∏aixi+1∑∑xi=m−2(m−2x1,x2,…,xn)∏aixi∏ai∏ai∑∑xi=m−2(m−2x1,x2,…,xn)∏aixi\sum_{\sum x_i = m - 2} \binom{m - 2}{x_1, x_2, \dots, x_n} \prod a_i^{x_i + 1}\\ \sum_{\sum x_i = m - 2} \binom{m - 2}{x_1, x_2, \dots, x_n} \prod a_i^{x_i} \prod a_i\\ \prod a_i \sum_{\sum x_i = m - 2} \binom{m - 2}{x_1, x_2, \dots, x_n} \prod a_i^{x_i}\\

发现后者实质上就是 Prufer 序列的总数，也就是 nm−2n^{m - 2}，方案数也就是 nm−2∏ain^{m - 2}\prod a_i，这也是一个经典结论。

Figures

考虑枚举 Prufer 序列，设第 ii 个联通块的点在枚举的 Prufer 序列里出现了 xix_i 次，那么答案为 ∑∏aixi+1‾\sum_{} \prod a_i^{\underline{x_i + 1}}。设 bib_i 为 ai−1a_i - 1，那么答案就为 ∑∏bixi‾∏ai\sum \prod b_i^{\underline{x_i}} \prod a_i。

考虑组合意义，∏bixi‾\prod b_i^{\underline{x_i}} 也就是在第 11 个连通块中顺序选出不重复的 x1x_1 个点，再在第 22 个连通块中顺序选出不重复的 x2x_2 个点，……，再在第 33 个连通块中顺序选出不重复的 xnx_n 个点。那么对于所有的 Prufer 序列，∑∏bixi‾\sum \prod b_i^{\underline{x_i}} 就相当于在整个图中按顺序选出不重复的 ∑xi=n−2\sum x_i = n - 2 个点，设 ∑bi\sum b_i 为 sumsum，则方案数为 ∑∏bixi‾∏ai=sumn−2‾∏ai\sum \prod b_i^{\underline{x_i}} \prod a_i = sum^{\underline{n - 2}} \prod a_i。