Prüfer 序列
\(n\) 个点的有标号无根树可以与一个长度为 \(n - 2\) 的 Prüfer 序列对应。
从树到 Prüfer 序列
- \(f\) 为空序列。
- 如果当前树上多于两个节点，假设当前标号最小的叶子为 \(x\)，与 \(x\) 相连的节点标号为 \(y\)，那么把 \(x\) 从树上删除，把 \(y\) 加入 \(f\) 末尾。
- 重复 2. 直到树上只有两个节点。
性质
- 在构造完 Prufer 序列后原树中会剩下两个节点，其中一个一定是编号最大的点 \(n\)。
- 每个节点在序列中出现的次数是其度数减 \(1\)，因此没有出现的就是叶节点。
实现
可以 \(O(n)\) 实现这个转换。
由于最后一定会留下 \(n\)，不妨钦定 \(n\) 为根（把 \(n\) 拎起来）。
定义：
- \(f_i\) 为 \(i\) 的父节点。
- \(d_i\) 为 \(i\) 的儿子数量。
- \(p_i\) 为 prufer 序列的第 \(i\) 项。
流程：
定义 \(i\) 表示当前编号最小的叶子的指针，\(cur\) 为当前序列填到哪一项。
- \(p_{cur} = f_i\)。
- 将 \(d_{p_{cur}}\) 减 \(1\)，表示删去 \(i\) 这个节点。
- 如果 \(d_{p_{cur}} = 0\) 且 \(p_{cur} < i\)，那么 \(p_{cur}\) 比当前最小值还要小，直接令 \(p_{cur + 1} = f_{p_{cur}}\) 。
void Tree_to_Prufer() {
for(int i = 1; i < n; ++ i) {
cin >> f[i];
++ d[f[i]];
}
for(int cur = 0, i = 1; cur < n - 2; ++ i) {
while(d[i]) ++ i;
p[++ cur] = f[i];
while(cur < n - 2 && -- d[p[cur]] == 0 && p[cur] < i) {
p[cur + 1] = f[p[cur]];
++ cur;
}
}
for(int i = 1; i <= n - 2; ++ i) cout << p[i] << ' ';
}
从 Prüfer 序列到树
- 找到当前不在 \(f\) 中且还未使用的最小元素 \(x\)。
- \(x\) 与 \(f\) 的第一个元素连边。
- 删除 \(f\) 的第一个元素，如果 \(f\) 非空，重复上述过程。
- 最后还剩两个点未使用，将他们连边。
代码实现类似。
void Prufer_to_Tree() {
for(int i = 1; i <= n - 2; ++ i) {
cin >> p[i];
++ d[p[i]]; // 以 $n$ 为根，儿子数量
}
p[n - 1] = n;
for(int cur = 1, i = 1; cur <= n - 1; ++ cur, ++ i) {
while(d[i]) ++ i;
f[i] = p[cur];
while(cur < n - 1 && -- d[p[cur]] == 0 && p[cur] < i) {
f[p[cur]] = p[cur + 1];
++ cur;
}
}
for(int i = 1; i <= n - 1; ++ i) cout << f[i] << ' ';
}
Caylay 定理
\(n\) 个点的有标号无根树有 \(n^{n -2}\) 种。
例题
P6086 【模板】Prufer 序列
P2290 [HNOI2004] 树的计数
题意：给定每个点的度数 \(d_i\)，求不同的有标号无根树个数。
相当于 \(d_i - 1\) 个 \(i\) 排进长为 \(n - 1\) 的序列的方案数。
即
\[\dfrac{(n - 1)!}{(d_1 - 1)!(d_2 - 1)!\cdots(d_n - 1)!} \]由于保证了答案小于 \(10^{17}\)，可以不用高精，全程用一个大于 \(10^{17}\) 的质数取模（如 \(4179340454199820289\)）。
特判无解，根据 prufer 序列的性质，一定有 \(\sum d_i - 1 = n - 2\)。
标签：标号,cur,++,笔记,学习,int,序列,计数问题,节点 From： https://www.cnblogs.com/Luxinze/p/18208159