浅谈 Prufer（Prüfer） 序列

· · 算法·理论

Part 0：前置知识

Part 1：什么是 Prufer 序列

从数学角度上来说，Prufer 序列是无根有标号树形结构的双射。即，由一个 Prufer 序列可以得到唯一的树，由一棵树可以得到唯一的 Prufer 序列。

它对树上计数问题和构造问题起到了很大的作用。

Prufer 序列主要解决这三类问题：

Part 2：Prufer 序列的构造和性质

2.1：如何构造 Prufer 序列

给定一棵树。每一次，我们都在树上找到编号最小的叶子节点，并记录下与它唯一相连的那个父节点的编号，然后将这个叶子节点及其相连的边从树上删除，更新度数。重复这个过程，直到树中只剩下最后 2 个节点为止。过程中记录的父节点编号序列就是 Prufer 序列。

例如，这是一棵 7 个结点的树的 Prufer 序列构建过程：

最终的 Prufer 序列为 [2, 2, 3, 3, 2]。

唯一性证明：

由于 Prufer 序列每一步选择编号最小的叶子节点，而不存在多个最小的叶子节点（编号不可能重复），所以此选择具有唯一性。那么，Prufer 序列是有唯一性的。

2.2：Prufer 序列的性质

性质 1：

在剩余的两个节点中，一定有编号为 n 的节点。

证明：

我们采用反证法进行推导，假设最后留存的两个节点均不包含编号为 n 的节点，那么节点 n 必然在之前的步骤中被当作叶子删除。

节点 n 是所有顶点里编号最大的点，只要图中还存在任意一个编号小于 n 的节点，n 就不可能成为全局编号最小的叶子，自然无法被选中并删除。

上述推论与最初假设相互矛盾，因此假设不成立。即，在剩余的两个节点中，一定有编号为 n 的节点。

性质 2：

设节点编号 i 在 Prufer 序列中出现的次数为 \text{cnt}_i，度数为 \text{deg}_i，则：

\text{cnt}_i + 1 = \text{deg}_i

即出现次数加上 1 为节点 i 的度数。

证明：

对任意标号节点 i，树中该点初始度数为 \text{deg}_i，每一次它作为相邻点被记录进 Prufer 序列，都对应有一个邻接的叶子节点被删除，这会让节点 i 的度数恰好减 1，因此序列中每出现一次 i，其度数就减少 1。

当构造流程终止时，树上仅剩两个节点，此时节点 i 若仍保留在树中，它的度数至少为 1；若已被删除，则它最后一次被记录时度数恰好降为 1，随后就会作为最小叶子被移除。无论哪种情况，节点 i 最终剩余的度数都恒为 1，也就意味着初始度数减去出现次数等于 1，即 \text{deg}_i - \text{cnt}_i = 1。

最后，移项得 \text{cnt}_i + 1 = \text{deg}_i。

Part 3：Prufer 序列和树的互转

3.1：树转 Prufer 序列

算法步骤见 2.1。

::::success[Code]

void ToPrufer() {
  fill(deg + 1, deg + n + 1, 1);  // 初始化，deg[i] = 1。
  for (int i = 1; i < n; ++ i) {
    ++ deg[fa[i]];
  }
  int cur; // 当前枚举到的最小编号节点
  for (int i = 1; i <= n; ++ i) {
    if (deg[i] == 1) {
      cur = i;
      break;
    }
  }
  int leaf = cur; // 编号最小的叶子节点
  for (int i = 1, f; i <= n - 2; ++ i) {
    f = fa[leaf], prufer[i] = f;
    -- deg[f];
    if (deg[f] == 1 && f < cur) {
      leaf = f;
      continue;
    }
    ++ cur;
    for (; deg[cur] != 1; ++ cur);
    leaf = cur;
  }
}

::::

3.2：Prufer 序列转树

如上文所述，在一个 Prufer 序列中，某个节点编号出现的次数加 1 等于它的度数。我们不停的找到编号最小的叶子结点，然后与 Prufer 序列中的结点依次连边，还原父子关系。注意，虽然我们描述了父子关系，但本质上这是一棵无根树。Prufer 序列只是对树的拓扑结构的映射。

算法步骤：

给定一个长度为 n - 2 的 Prufer 序列 p，还原出对应的 n 个节点的有标号树。

  1. 初始化一个数组 \text{deg}（即度数），设所有初始值为 1。
  2. 遍历 Prufer 序列，对于序列 p 中的每个元素 x ，令 \text{deg}_i \to \text{deg}_i + 1，这样就得到了每个点的度数。
  3. 找到编号最小的度数为 1 的结点，其父节点就是 p_1，连边，并将 \text{deg}_{p_i} \to \text{deg}_{p_i} - 1。
  4. 重复步骤 3，直到处理完所有 n - 2 个 p 中的元素，最后剩下 2 个结点连边即可。由于是无根有标号树，所以最后谁是根节点不影响。

::::success[Code]

void ToTree() {
  fill(deg + 1, deg + n + 1, 1); // 初始化，deg[i] = 1。
  for (int i = 1; i <= n - 2; ++ i) {
    ++ deg[prufer[i]];
  }
  int cur;
  for (int i = 1; i <= n; ++ i) {
    if (deg[i] == 1) {
      cur = i;
      break;
    }
  }
  int leaf = cur;
  for (int i = 1, f; i <= n - 2; ++ i) {
    fa[leaf] = prufer[i], f = fa[leaf];
    -- deg[f];
    if (deg[f] == 1 && f < cur) {
      leaf = f;
      continue;
    }
    ++ cur;
    for (; deg[cur] != 1; ++ cur);
    leaf = cur;
  }
  fa[n] = leaf;
}

::::

Part 4：Cayley 公式及其推广

Cayley 公式是 Prufer 序列的一个核心应用。

公式 1：

**证明：** 根据 Prufer 序列的构成，$n$ 个节点的有标号树与长度为 $n - 2$ 的 Prufer 序列一一对应。 而长度为 $n - 2$ 的序列，每个位置可以取 $1$ 至 $n$ 中的任意一个数，共有 $n^{n - 2}$ 种可能。因此，$n$ 个节点的有标号树的数量为 $n^{n - 2}$。 每棵无根树可以选任意一个节点当根，共 $n$ 种选择。所以，有根树数量为 $n^{n - 2} \times n = n^{n - 1}$。 **公式 2：** 对于 $n$ 个节点的完全图，其生成树的方案数为 $n^{n - 2}$。 **证明：** 任何一个生成树都可以由长度为 $n - 2$ 的值域为 $[1, n]$ 的 Prufer 序列映射得到。 由乘法原理，得到方案数为 $n^{n - 2}$。 **公式 3：** 对于 $n$ 个节点的树，点 $i$ 的度数为 $\text{deg}_i$，则满足条件的树的数量为： $$\frac{(n - 2)!}{\prod_{i = 1}^n (\text{deg}_i - 1)!}$$ **证明：** 根据 Prufer 序列的性质 2，可以得到 $\text{cnt}_i = \text{deg}_i - 1$，即出现次数为点的度数减去 $1$。 所以，问题转化为：在长度为 $n - 2$ 的序列中，需要出现 $\text{deg}_i - 1$ 个节点 $i$，这样的序列有多少个。 这是多重集的排列数问题，详见作者写的 [浅谈排列组合](https://www.luogu.com.cn/article/1kutt8hl)。 套公式即可得到答案为： $$\frac{(n - 2)!}{(\text{deg}_1 - 1)!(\text{deg}_2 - 1)! \cdots (\text{deg}_n - 1)!}$$ 得证。 ## Part 5：例题 ### [P6086 【模板】Prüfer(Prufer) 序列](https://www.luogu.com.cn/problem/P6086) 模板题。 ::::success[Code] ```cpp #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; const int kMaxN = 5e6 + 10; int n, m; ll fa[kMaxN], prufer[kMaxN], deg[kMaxN], ans; void ToPrufer() { fill(deg + 1, deg + n + 1, 1); // 初始化，deg[i] = 1。 for (int i = 1; i < n; ++ i) { ++ deg[fa[i]]; } int cur; // 当前枚举到的最小编号节点 for (int i = 1; i <= n; ++ i) { if (deg[i] == 1) { cur = i; break; } } int leaf = cur; // 编号最小的叶子节点 for (int i = 1, f; i <= n - 2; ++ i) { f = fa[leaf], prufer[i] = f; -- deg[f]; if (deg[f] == 1 && f < cur) { leaf = f; continue; } ++ cur; for (; deg[cur] != 1; ++ cur); leaf = cur; } } void ToTree() { fill(deg + 1, deg + n + 1, 1); // 初始化，deg[i] = 1。 for (int i = 1; i <= n - 2; ++ i) { ++ deg[prufer[i]]; } int cur; for (int i = 1; i <= n; ++ i) { if (deg[i] == 1) { cur = i; break; } } int leaf = cur; for (int i = 1, f; i <= n - 2; ++ i) { f = fa[leaf] = prufer[i]; -- deg[leaf], -- deg[f]; if (deg[f] == 1 && f < cur) { leaf = f; continue; } ++ cur; for (; deg[cur] != 1; ++ cur); leaf = cur; } fa[n] = leaf; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> m; if (m == 1) { for (int i = 1; i < n; ++ i) { cin >> fa[i]; } ToPrufer(); for (ll i = 1; i <= n - 2; ++ i) { ans ^= (i * prufer[i]); } cout << ans << '\n'; } else { for (int i = 1; i <= n - 2; ++ i) { cin >> prufer[i]; } ToTree(); for (ll i = 1; i < n; ++ i) { ans ^= (i * fa[i]); } cout << ans << '\n'; } return 0; } ``` :::: ### [P2290 [HNOI2004] 树的计数](https://www.luogu.com.cn/problem/P2290) Cayley 公式，满足条件的树的数量为： $$\frac{(n - 2)!}{\prod_{i = 1}^n (d_i - 1)!}$$ 但本题的 $n$ 可以达到 $150$，暴力计算 $(n - 2)!$ 的阶乘肯定会炸掉。 第一种写法肯定是高精度。 第二种写法比较好想。从数据范围可以得到，本题答案不超过 $10^{17}$。这可以想到什么？当然是取模了！那么，我们便可以设一个质数模数 $p = 10^{17} + 3$，然后每一次计算都对 $p$ 取模即可。 第三种写法较为小众，运用了勒让德定理。 对于质数 $p$，在 $n!$ 中包含的 $p$ 的指数： $$\sum_{i = 1}^{\infty} \frac{n}{p^i}$$ 对分子分母进行拆解即可。 因为第一种写法太长，第三种写法太麻烦，所以作者运用第二种写法。 请记得判无解（度数减 $1$ 之和不等于 $n - 2$）和 $n \le 2$ 的情况。 需要开 `__int128`。 ::::success[Code] ```cpp #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; const int kMaxN = 5e6 + 10; const __int128 kMod = (ll)1e17 + 3; ll n, d[kMaxN], sum; __int128 f[kMaxN], ans; __int128 Qpow(__int128 a, __int128 b) { __int128 ans = 1; for (; b; b >>= 1) { if (b & 1) { ans = ans * a % kMod; } a = a * a % kMod; } return ans; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n, f[0] = 1; for (int i = 1; i <= n; ++ i) { cin >> d[i], sum += d[i] - 1; } if (n == 1) { return cout << !d[1] << '\n', 0; } else if (n == 2) { return cout << (d[1] == 1 && d[2] == 1) << '\n', 0; } if (sum != n - 2) { return cout << "0\n", 0; } for (int i = 1; i <= 150; ++ i) { f[i] = f[i - 1] * i % kMod; } ans = f[n - 2]; for (int i = 1; i <= n; ++ i) { if (d[i] != 1) { ans = ans * Qpow(f[d[i] - 1], kMod - 2) % kMod; } } cout << (ll)ans << '\n'; return 0; } ``` :::: ### [CF156D Clues](https://www.luogu.com.cn/problem/CF156D) 这是 Cayley 公式的一种扩展形式。 **题目翻译（中译中）：** 给定一个有 $n$ 个点的图，它被分成了 $k$ 个连通块，每个连通块里有 $s_1, s_2, \dots, s_k$ 个点，问用最少的边把整个图连成一棵树（也就是把这 $k$ 个连通块连起来变成一棵“块树”），总共有多少种连法？ **Solution：** 我们先把每个连通块看成一个整体，也就是一个“超级节点”。要把 $k$ 个超级节点连成一棵树，一共需要 $k - 1$ 条边。 而树的边数等于所有节点度数和的一半，所以这棵“块树”的总度数和是 $2(k - 1)$。 我们记第 $i$ 个连通块在这棵树里的度数是 $d_i$，那么所有连通块的度数加起来就是 $2k - 2$。 普通的 Prufer 序列可以用来数普通树的数量，这里我们用它来数“块树”的结构数。 对于一组度数 $d_1, d_2, \dots, d_k$，对应的 Prufer 序列构造方法数，就等于把 $k - 2$ 个位置分配给各个连通块，让第 $i$ 个连通块出现 $d_i - 1$ 次的排列数。 Prufer 序列只决定了块与块之间的连接结构，但是具体到两个连通块之间的边，要从哪个点连到哪个点呢？ + 第 $i$ 个连通块的度数是 $d_i$，说明它要连出 $d_i$ 条边，每条边的起点都可以选这个连通块里的任意一个点，所以有 $s_i^{d_i}$ 种选法。 + 把所有连通块的选法乘起来，就是给定度数序列时，完整的连边方案数。 现在我们要把所有可能的度数序列 $d_1, d_2, \dots, d_k$ 对应的方案数全部加起来。这个求和看起来很复杂，但可以用“多项式定理”来简化。 我们做个变量替换，令 $e_i = d_i - 1$，这样度数和的条件就变成了 $e_1 + e_2 + \dots + e_k = k-2$。 把 $d_i = e_i + 1$ 代入后，求和式刚好可以看成是多项式展开的形式： $$(s_1 + s_2 + \dots + s_k)^{k - 2} \times s_1 s_2 \cdots s_k$$ 而 $s_1 + s_2 + \dots + s_k = n$（总点数），所以最后就化简成了： $$n^{k - 2} \times \prod_{i = 1}^k s_i$$ 代码不给了。