跳转至

Prufer 序列

定义 对于 \(n\ge 2\)，Prufer 序列是一个长为 \(n-2\)，值域为 \([1,n]\) 的序列。

定理 Prufer 序列和 \(n\)（\(n\ge 2\)）个节点的有标号无根树（两棵树不同当且仅当存在 \((u,v)\) 在 \(T_1\) 上有边而在 \(T_2\) 上没边）存在一一映射关系。也就是说，\(n\)（\(n\ge 1\)）个节点的有标号无根树数量等于 \(n^{n-2}\)。

首先考虑如何从树构造序列。我们每次取出编号最小的叶子节点，将它父亲的编号加入到序列的末尾，然后删去这个叶子，直到树上只剩两个点。这显然是一个长为 \(n-2\)，值域为 \(n\) 的序列。

然后考虑如何从序列构造树。不难发现树上每个节点的度数等于它在 Prufer 序列中的出现次数 +1。于是我们可以知道初始时哪些节点是叶子，从而知道第一个被删除的叶子，于是我们得到了一条边。剩下的部分显然是一个子问题。

推论 如果一条连接 \((u,v)\) 的边有 \(sz[u]sz[v]\) 种方案，那么把 \(k\) 个点连成树的方案数等于

\[ \bigg(\prod_{i=1}^{k}sz[i]\bigg)\bigg(\sum_{i=1}^{k}sz[i]\bigg)^{k-2} \]

发现其实就是给方案数乘以了 \(\prod sz[i]^{deg(i)}\)，而 \(deg(i)\) 就是序列中出现次数加一，因此不难写出上式。

Prufer 序列的线性求解和树的构造

记 \(S\) 表示当前的全体叶子，\(T\) 表示父亲已经确定的点，注意到 \(S\) 是 \(S\cup T\) 的一个后缀加前面最多一个点。只需记一个指针表示后缀的位置，一个度数数组，再开一个变量标记当前最小叶子。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 5e6 + 10;

struct Edge {
    int v, next;
} pool[2 * N]; int ne, head[N];
inline void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]}, head[u] = ne;
}

int n, tp;
int fa[N], deg[N], p[N]; ll ans;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> tp;
    if(tp == 1) {
        for(int i = 1; i <= n - 1; i++) {
            cin >> fa[i]; ++deg[i], ++deg[fa[i]];
            addEdge(fa[i], i), addEdge(i, fa[i]);
        }
        int cur = 1, cnt = 0, mn = 0;
        while(deg[cur] != 1) ++cur; mn = cur;
        while(cnt < n - 2) {
            p[++cnt] = fa[mn], deg[mn] = 0;
            while(deg[cur] != 1) ++cur;
            if(--deg[fa[mn]] == 1) mn = min(cur, fa[mn]);
            else mn = cur;
        }
        for(int i = 1; i <= n - 2; i++) ans ^= (ll)i * p[i];
        // for(int i = 1; i <= n - 2; i++) cout << p[i] << ' '; cout << '\n';
    } else {
        for(int i = 1; i <= n; i++) deg[i] = 1;
        for(int i = 1; i <= n - 2; i++) cin >> p[i], deg[p[i]]++;
        int cur = 1, cnt = 0, mn = 0; p[n - 1] = n;
        while(deg[cur] != 1) ++cur; mn = cur;
        while(cnt < n - 1) {
            fa[mn] = p[++cnt], deg[mn] = 0;
            while(deg[cur] != 1) ++cur;
            if(--deg[fa[mn]] == 1) mn = min(cur, fa[mn]);
            else mn = cur;
        }
        for(int i = 1; i <= n - 1; i++) ans ^= (ll)i * fa[i];
        // for(int i = 1; i <= n - 1; i++) cout << fa[i] << ' '; cout << '\n';
    }
    cout << ans << '\n';

    return 0;
}

P6086 【模板】Prüfer（Prufer）序列