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

## Prufer 序列 Prufer 序列可以将一个带标号 $n$ 个节点的树用 $[1,n]$ 中的 $n-2$ 个整数表示，即 **$n$ 个点的完全图的生成树**与**长度为 $n-2$ 值域为 $[1,n]$ 的数列**构成的双射。 Prufer 序列可以方便的解决一类树相关的计数问题，比如[凯莱定理](https://www.luogu.com.cn/problem/UVA10843)：$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 序列](https://www.luogu.com.cn/problem/P6086) ```cpp 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; } ```