Prufer 序列实际上是一种转化的产物，这种转化使得一棵有 \(n\) 个点的无根树可以在线性时间内与一个有 \(n-2\) 个元素，且序列中元素权值在 \([1,n]\) 中的序列互相转化。
它与单纯的父节点组成的序列区别在于：对于每棵树，它的 Prufer 序列是唯一的，每一个 Prufer 序列也对应着唯一一棵树。换句话说，树与 Prufer 序列是双射关系。
Prufer 序列强大的地方就在这里。把一棵树转化为一个序列，而序列的计数难度明显小于树的计数。
由树转化成 Prüfer 序列
先给出转化的步骤：
- 寻找到当前最小的叶子节点 \(u\)。
- 把 \(u\) 的父亲加入 Prüfer 序列。
- 从树上删去 \(u\)。
- 重复前三个步骤，直到 Prüfer 序列有 \(n-2\) 个数。此时原树必定只剩下两个点。
一个显然的想法是使用小根堆，时间复杂度为 \(O(n\log n)\)。但是在这里我们有线性做法：
- 找到当前最小叶子节点 \(u\)。
- 把 \(u\) 的父亲 \(fa\) 加入 Prüfer 序列，并将 \(fa\) 的度数减少 \(1\)。
- 如果 \(fa\) 的度数变为 \(1\)，且 \(fa<u\)，那么将 \(fa\) 的父亲 \(h\) 加入 Prüfer 序列。因为此时 \(fa\) 必定为最小叶子（\(u\) 本来为最小叶子，但是 \(fa\) 比 \(u\) 还小。在删去 \(u\) 的过程中没有除 \(fa\) 以外的新叶子产生，所以 \(fa\) 为最小叶子）。
- 重复第三步，每次都跟 \(u\) 比较。直到有一个不符合条件。此时增加 \(u\)。
- 重复前四步，直到 Prüfer 序列有 \(n-2\) 个数，此时原树必定只剩下两个点。
for (int i = 1; i <= n; ++i) deg[fa[i]]++;
static int check[N], tot;
for (int i = 1; i <= n; ++i) if (deg[i] == 0) check[i] = 1;
for (int mn = 1; mn < n; ++mn) {
int u = mn;
while (check[u] == 1) {
p[++tot] = fa[u];
if (tot == n - 2) break;
check[u] = 0;deg[fa[u]]--;
if (deg[fa[u]] == 0) {
check[fa[u]] = 1;
if (mn > fa[u]) u = fa[u];
}
}
if (tot == n - 2) break;
}
Prüfer 序列的性质
- Prufer 序列中每个点出现的次数代表它有几个儿子，即度数 \(+1\)。
由 Prüfer 序列还原树
先给出还原步骤：
- 找到当前最小的，不在序列中的点 \(u\)，序列中的下标最小点 \(v\) 即为 \(u\) 的父亲。
- 删除序列中的第一个 \(v\)。
- 重复以上步骤，最后会留下最大点和一个点 \(u\)。在一般题目里我们不妨设最大点为无根树的假想根，那么最后的步骤是将 \(u\) 连向最大点。
类似于树转 Prüfer 序列，我们也有线性方法：
- 找到当前最小的，不在序列中的点 \(u\)，序列中下标最小的点 \(v\) 即为 \(u\) 的父亲。
- 删除序列中的第一个 \(v\)，如果 \(v\) 删除后不再在序列中出现，且 \(v<u\)，那么 \(v\) 的父亲即为序列中下标最小的点的父亲。
- 重复步骤二，每次与 \(u\) 比较，直到有一个不符合条件。此时增加 \(u\)。
- 重复以上步骤，直到 Prüfer 序列为空。
for (int i = 1; i <= n - 2; ++i) deg[p[i]]++;
static int tot;
for (int mn = 1; mn < n; ++mn) {
int u = mn;
while (deg[u] == 0) {
fa[u] = p[++tot];
deg[u] = 1;
if (tot == n - 2) break;
deg[fa[u]]--;
if (deg[fa[u]] == 0) if (mn > fa[u]) u = fa[u];
}
if (tot == n - 2) break;
}
for (int i = 1; i < n; ++i) if (fa[i] == 0) fa[i] = n;