自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 22:17:15，当前版本为作者最后更新于2020-02-12 00:15:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}