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

· · 题解

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