Prufer 序列

定义

Prufer 序列可以将一个带标号 n 个结点的树用 [1,n] 中的 n-2 个整数表示。可以把它理解为完全图的生成树与数列之间的双射。

建立方法：每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 n-2 次后就只剩下两个结点，算法结束。

性质

1. 在构造完 Prufer 序列后原树中会剩下两个结点，其中一个一定是编号最大的点 。
2. 每个结点在序列中出现的次数是其度数减 1 。（没有出现的就是叶结点）

线性构造方法

首先发现，叶结点数是非严格单调递减的。要么删一个，要么删一个得一个。

具体而言，用一个指针指向编号最小的度数为 1 的节点。每次将它与当前枚举到的 Prufer 序列的点连接之后，如果产生了新的度数为 1 的节点且编号比当前指针指向的更小，则直接继续将它与下一个 Prufer 序列的点连接，否则自增找到下一个编号最小的度数为 1 的节点。

模版题

洛谷P6086 【模板】Prufer 序列
实现 Prufer 序列和父亲序列的相互转化。（假定以 n 号节点为根）

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> fa, prufer;
vector<int> deg;

void getPrufer() {
    prufer.resize(n - 1);
    for (int i = 1, j = 1; i <= n - 2; i++, j++) {
        while (deg[j]) {
            j++;
        }
        prufer[i] = fa[j];
        while (i <= n - 2 && !(--deg[prufer[i]]) && prufer[i] < j) {
            prufer[i + 1] = fa[prufer[i]];
            i++;
        }
    }
}

void getFa() {
    fa.resize(n);
    for (int i = 1, j = 1; i < n; i++, j++) {
        while (deg[j]) {
            j++;
        }
        fa[j] = prufer[i];
        while (i < n && !(--deg[prufer[i]]) && prufer[i] < j) {
            fa[prufer[i]] = prufer[i + 1];
            i++;
        }
    }
}

long long solve(vector<int> &a) {
    long long ret = 0, sz = a.size();
    for (int i = 1; i < sz; i++) {
        ret ^= 1LL * i * a[i];
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    scanf("%d%d", &n, &m);
    if (m == 1) {
        fa.resize(n);
        deg.resize(n);
        for (int i = 1; i < n; i++) {
            scanf("%d", &fa[i]);
            deg[fa[i]]++;
        }
        getPrufer();
        printf("%lld\n", solve(prufer));
    }
    else {
        prufer.resize(n);
        deg.resize(n);
        for (int i = 1; i <= n - 2; i++) {
            scanf("%d", &prufer[i]);
            deg[prufer[i]]++;
        }
        prufer[n - 1] = n;
        getFa();
        printf("%lld\n", solve(fa));
    }
    return 0;
}

Cayley 公式

内容：完全图 K_n 有 n^{n-2} 棵生成树。

证明：任意一个长度为 n-2 的值域 [1,n] 的整数序列都可以通过 Prufer 序列双射对应一个生成树，于是方案数就是 n^{n-2} 。

多项式定理

相关定义

定义记号：

\binom{n}{n_1,n_2,\cdots,n_t}=\frac{n!}{n_1!n_2!\cdots n_t!}

其中 n_1+n_2+\cdots +n_t=n。

意义：将 n 个元素分为 t 组，使得第 i 组有 n_i 个元素的方案数。

定理内容

(x_1 + \dots + x_m)^n = \sum_{c_i \ge 0,\sum_{i=1}^m c_i = n}\binom{n}{c_1, c_2, \cdots ,c_m}\cdot \prod_{i=1}^m{x_i}^{c_i}

与 Prufer 序列的关联

问题：给定 n 个点，以及其最终的度数 d_i，你可以任意连线，问最终能产生多少棵符合答案的树？

分析：n 个点的树 Prufer 序列长度为 n-2，对于每个度数为 d_i 的点，它在 Prufer 序列中出现了 d_i-1 次。因此答案为：

\binom{n-2}{d_1-1,d_2-1,\cdots,d_n-1}

例题

1. 2020牛客暑期多校第七场 I. Valuable Forests

2. CF156D Clues