Prufer 序列

用途

对于一颗有根树，我们想要把它映射到一个值域为 [1, n] 整数序列上，且是双向映射，并用它来解决一些神奇的问题，映射出来的序列就是 Prufer 序列。

做法

构造 Prufer

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

显然使用堆可以做到 O(nlog n) 的复杂度，代码不放了，要写自己写。

思考如何优化，发现了一个神奇算法，它可以在 O(n) 内构造 Prufer 编码。

该算法的核心思想是使用一个移动指针，该指针始终指向当前我们希望移除的叶子节点。

乍看之下这似乎不可能实现，因为在构建 Prufer 编码的过程中，叶子节点的编号可能增加或减少。然而仔细观察后会发现，实际情况并非如此。叶子节点的数量不会增加，只会减少一个（移除一个叶子节点且不产生新叶子）或保持不变（移除一个叶子节点并产生另一个叶子），这意味着叶子结点个数单调不增。

在第一种情况下，只能通过搜索下一个最小叶子节点来处理。但在第二种情况下，如果我们能够判断新生成的叶子节点是否可用，则可以在 O(1) 时间内决定是继续使用这个新叶子节点，还是需要搜索下一个最小叶子节点。而大多数情况下，我们可以直接使用新生成的叶子节点。

为实现这一点，我们使用变量 ptr。该变量表示在编号 1 到 ptr 的顶点集合中，最多存在一个叶子节点（即当前叶子节点）。该范围内的其他顶点要么已被移除，要么仍保留多个相邻顶点。同时，我们假设尚未移除任何编号大于 ptr 的叶子节点。

这一变量在第一种情况下非常有用。移除当前叶子节点后，由于 1 到 ptr 范围内不可能存在其他叶子节点，我们可以直接从 ptr + 1 开始搜索下一个叶子节点，而无需回溯到顶点 1。在第二种情况下，我们进一步细分两种情况：

• 若新生成的叶子节点编号小于 ptr，则它必定是下一个叶子节点（因为已知小于 ptr 的范围内无其他叶子节点）。
• 若新生成的叶子节点编号更大，则其必然大于 ptr，此时可再次从 ptr + 1 开始搜索。

尽管可能需要多次线性搜索下一个叶子节点，但由于指针 ptr 始终单向递增，总时间复杂度仍为 O(n)。

vector<vector<int>> adj;
vector<int> parent;

void dfs(int v) {
    for (int u : adj[v]) {
        if (u != parent[v]) {
            parent[u] = v;
            dfs(u);
        }
    }
}

vector<int> pruefer_code() {
    int n = adj.size();
    parent.resize(n);
    parent[n-1] = -1;
    dfs(n-1);

    int ptr = -1;
    vector<int> degree(n);
    for (int i = 0; i < n; i++) {
        degree[i] = adj[i].size();
        if (degree[i] == 1 && ptr == -1)
            ptr = i;
    }

    vector<int> code(n - 2);
    int leaf = ptr;
    for (int i = 0; i < n - 2; i++) {
        int next = parent[leaf];
        code[i] = next;
        if (--degree[next] == 1 && next < ptr) {
            leaf = next;
        } else {
            ptr++;
            while (degree[ptr] != 1)
                ptr++;
            leaf = ptr;
        }
    }

    return code;
}

代码中，我们首先为每个顶点找到其父节点 parent[i]，即该顶点被移除时的直接关联节点。通过将树根节点设为 n（该节点永远不会被移除），我们可以通过深度优先搜索（DFS）确定这一关系。同时计算每个顶点的度数。指针 ptr 表示剩余叶子节点中的最小可能编号（当前叶子节点 leaf 除外）。当新生成的叶子节点满足条件（度数减为 1 且编号小于 ptr）时，我们直接使用该节点；否则，通过递增指针进行线性搜索。

显然，该算法的时间复杂度为 O(n)。

Prufer 转树

我们观察一下刚才的序列有什么性质。

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

根据 Prufer 序列的性质，我们可以得到原树上每个点的度数。然后你也可以得到编号最小的叶结点，而这个结点一定与 Prufer 序列的第一个数连接。然后我们同时删掉这两个结点的度数。

每次我们选择一个度数为 1 的最小的结点编号，与当前枚举到的 Prufer 序列的点连接，然后同时减掉两个点的度。到最后我们剩下两个度数为 1 的点，其中一个是结点 n。就把它们建立连接。使用堆维护这个过程，在减度数的过程中如果发现度数减到 1 就把这个结点添加到堆中，这样做的复杂度是 O(nlog n) 的。

同刚才的线性做法，我们也可以在线性复杂度内构造树。在删度数的时侯会产生新的叶结点，于是判断这个叶结点与指针 p 的大小关系，如果更小就优先考虑它。

vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
    int n = code.size() + 2;
    vector<int> degree(n, 1);
    for (int i : code)
        degree[i]++;

    int ptr = 0;
    while (degree[ptr] != 1)
        ptr++;
    int leaf = ptr;

    vector<pair<int, int>> edges;
    for (int v : code) {
        edges.emplace_back(leaf, v);
        if (--degree[v] == 1 && v < ptr) {
            leaf = v;
        } else {
            ptr++;
            while (degree[ptr] != 1)
                ptr++;
            leaf = ptr;
        }
    }
    edges.emplace_back(leaf, n-1);
    return edges;
}

模板题

用途

很多，例如证明 Cayley 公式（完全图 K_n 有 n^n − 2 棵生成树，模版）啊，给定每个点的度数，求有多少棵符合条件的树啊，等等。

现在我们来看这样一道题。

一个 n 个点 m 条边的带标号无向图有 k 个连通块。我们希望添加 k − 1 条边使得整个图连通。求方案数。

容易想到将每一个联通块合并考虑，那么我们就可以于是设 d_i 为第 i 个连通块的度数。

容易想到 $\sum_{i=1}^kd_i=2k-2$，所以对于一个给定的 d 构造 Prufer 序列的方案数是 $\displaystyle\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}=\frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdots(d_k-1)!}$。

对于第 i 个连通块，它的连接方式有 s_i^d_i 种，因此对于给定 d 序列使图连通的方案数是

$$ \binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot \prod_{i=1}^k{s_i}^{d_i} $$

现在我们要枚举 d 序列，式子变成

$$ \sum_{d_i\ge 1，\sum_{i=1}^kd_i=2k-2}\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot \prod_{i=1}^k{s_i}^{d_i} $$

二项式定理会吧。

$$ (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i $$

扩展一下。

$$ (\sum_{i=1}^{m}x_i)^p = \sum_{\substack{c_i \ge 0 ,\ \sum_{i=1}^m c_i = p}} \binom{p}{c_1, c_2, \cdots ,c_m}\cdot \prod_{i=1}^m{x_i}^{c_i} $$

那么我们对原式做一下换元，设 e_i = d_i − 1，显然 $\sum_{i=1}^ke_i=k-2$，于是原式变成

$$ \sum_{e_i\ge 0，\sum_{i=1}^ke_i=k-2}\binom{k-2}{e_1,e_2,\cdots,e_k}\cdot \prod_{i=1}^k{s_i}^{e_i+1} $$

化简得到

$$ (\sum_{i=1}^{k}s_i)^{k-2}\cdot \prod_{i=1}^ks_i $$

即

$$ n^{k-2}\cdot\prod_{i=1}^ks_i $$