Prufer 序列学习笔记

注：这是一个散片笔记，内容较少。

$Prufer$ 序列是一种可以方便的进行图上计数的序列。最早被拿来证明凯莱定理。

$Prufer$ 序列必须在无根树上构造，构造方法：

每次选择一个编号最小的叶子节点，将它从树上删除，同时将与它相连的点（由于是无根树，所以这样表示，也就是它的父亲）加入序列。
重复这一过程直到序列长度为 $n - 2$ 。

简单性质：

一个点在 $Prufer$ 序列中出现的次数等价于它的度数 $-1$ 。
最后剩下的 $2$ 个点中，必然包括 $n$ 号节点。
每个无根树与它的 $Prufer$ 序列成双射关系。

所以这个东西也可以被用来对拍，因为 $Prufer$ 序列一定合法且可以对应一棵树。

$Prufer$ 序列的线性构造

用上面的定义进行构造，用堆维护最小值显然是可以的，但复杂度不够优。

因为 $Prufer$ 序列是按照特殊的权值编号来构造的，所以就会有的特殊性质。

具体实现：

顺序遍历数组，找到叶子节点 $y$ 。
找到之后将它的父亲加进 $Prufer$ 序列，将父亲节点度数 $-1$ 。如果父亲节点变成了叶子节点，设父亲的父亲的编号为 $x$ ，按照 $x$ 和 $y$ 的大小关系进行分类讨论：
1. $x > y$ 之后一定会扫到 $x$ ，所以不用进行任何操作。
并且也不能进行任何操作，因为 $[x + 1, y - 1]$ 可能有叶子节点 $z$ ，这时候显然是先要处理 $z$ ，再处理 $y$ 的。
1. $x < y$ 这个时候需要直接将 $x$ 设为 $y$ 并直接重复进行 $2.2$ （如果满足条件的话）。
  
  注：为了保证复杂度，不能直接将 $y$ 改变，而是应该采用别的方法，如利用 $p_y = x$ 不断地利用 $p$ 数组进行更新。

这样整个算法下来，每个点只会被删除一次，并且已经被删除的点不会被重复扫到，所以时间复杂度是线性的。

代码实现：

// Prufer 序列 学习笔记
// Prufer 序列的线性构造
void build (int n) {
  memset (p, 0, sizeof (p));
  for (int i = 1, j = 1; i <= n - 2; ++i, ++j) {
    while (d[j]) ++j;
    p[i] = f[j];
    // 一定要先修改 d[] 再进行编号判断
    while (i <= n - 2 && --d[p[i]] == 0 && p[i] < j) 
      p[i + 1] = f[p[i]], ++i;
  }
}

$Prufer$ 重构树与线性实现

因为 $Prufer$ 序列与树双射，所以可以将它映射回树。

首先要把 $p[n - 1]$ 赋成 $n$ ，因为考虑正着求 $Prufer$ 序列第 $n - 1$ 项一定是 $n$ ，只是因为它没有用所以跳过了而已。

然后直接跑一边，把所有赋值语句都左右交换。

代码实现：

// Prufer 序列 学习笔记
// Prufer 重构树与线性实现
void rebuild (int n) {
  memset (f, 0, sizeof (f));
  p[n - 1] = n;
  for (int i = 1, j = 1; i <= n - 1; ++i, ++j) {
    while (d[j]) ++j;
    f[j] = p[i];
    // 一定要先修改 d[] 再进行编号判断
    while (i <= n - 1 && --d[p[i]] <= 0 && p[i] < j)
      f[p[i]] = p[i + 1], ++i;
  }
}

性质：

首先是用来被证明的凯莱公式：完全图 $Kn$ 有 $n^{n - 2}$ 个生成树。

一个 $prufer$ 对应一棵树，长度为 $n - 2$ 值域为 $[1, n]$ 因此有 $n^{n - 2}$ 个生成树。
一个 $n$ 个点 $m$ 条边的无向图，有 $k$ 个连通块，想通过 $k - 1$ 条边将他连成连通图。设每个连通块的大小为 $s_i$ ，方案数为 $n^{k - 2}\cdot \prod_{i = 1}^k s_i$ 。

首先，感性理解是很好理解的，每个连通块向外连边的方案数为点数，内部联通情况为 $n^{k - 2}$ ,证明：

设 $d_i$ 表示第 $i$ 个连通块的度数。很容易发现：

$\sum_{i = 1}^k d_i = 2k - 2$

那么方案数为

$\sum_{\sum_{i = 1}^k d_i}\binom{k - 2}{d_1 - 1, d_2 - 1, \cdots, d_k - 1}\cdot\prod_{i = 1}^k s_i^{d_i} \\ \text{化简为} \sum_{2k - 2}\binom{k - 2}{d_1 - 1, d_2 - 1, \cdots, d_k - 1}\cdot\prod_{i = 1}^k s_i^{d_i} \\ \text{换元，设} e_i = d_i - 1, \\ \sum_{k - 2}\binom{k - 2}{e_1, e_2, \cdots, e_k}\cdot\prod_{i = 1}^ks_i^{e_i + 1} \\ \text{带入二项式定理} (s_1 + s_2 + \cdots + s_k)^{k - 2}\cdot\prod_{i - 1}^ks_i \\ n^{k - 2}\cdot\prod_{i = 1}^ks_i$

本文作者：CloudySky
写作时间： 2022-01-18
最后更新时间： 2022-01-18
遵循协议： BY-NC-SA

CloudySky || AFO

永远相信美好的事情即将发生。

Prufer 序列学习笔记