大部分都是贴网上的。
Prüfer 序列是一个长度为 \(n-2\)，值域为 \([1,n]\) 的整数序列。
每棵树必定存在 Prüfer 序列且唯一，每个 Prüfer 序列对应的树也必定存在且唯一，即二者为双射关系。
Prüfer 序列是这样从树转化的：
① 从树上选择编号最小的叶子节点，序列的下一位为其父节点的编号。
② 删去该叶子节点。
③ 重复 ① 和 ②，直到树只剩下两个节点，此时序列的长度刚好为 \(n-2\)
。
由 Prüfer 序列构造的过程，我们可以发现其具有两个显而易见的性质。
-
构造完后剩下的两个节点里，一定有一个是编号最大的节点。
-
对于一个 \(n\) 度的节点，其必定在序列中出现 \(n-1\) 次，因为每次删去其子节点它都会出现一次，最后一次则是删除其本身。一次都未出现的是原树的叶子节点。
由 Prüfer 序列重构树：
① 选择编号最小的叶子节点（即未出现在序列中的节点），其父节点就是序列的第 \(i\)（\(i\) 初始为1）个元素。
② 由性质可得，其父节点的度数为其出现次数 \(+1\)。将该叶子节点删去，其父节点度数 \(-1\)。若度数变成 \(1\)，则父节点也成为叶子节点。
③ 将 \(i\) 加一，然后重复 ① 和 ②，直到序列的每一个元素都使用完毕。
\(\text{应用}\)
- 无向完全图的不同生成树数：
若该完全图有 \(n\) 个节点，则任意一个长度为 \(n-2\) 的 Prüfer 序列都可以重构出其一棵生成树，且各不相同。又因为 Prüfer 序列的值域在 \([1,n]\)，故总数为 \(n^{n-2}\)。
这就是有名的 \(Cayley\) 公式。
- \(n\) 个点的无根树计数：
同上问题。
-
\(n\) 个点的有根树计数：
对每棵无根树来说，每个点都可能是根，故总数为 \(n^{n-1}\)。 -
\(n\) 个点，每点度分别为 \(a_i\) 的无根树计数：
总排列为 \((n-2)!\)，其中数字 \(i\) 出现了 \(a_i-1\) 次，故其重复的有 \((a_i-1)!\) 种排列。
应当除去重复的，故总个数为 \(\frac{(n-2)!}{\prod (a_i-1)!}\)。
代码，\(m=1\) 为树转 Prüfer ，\(m=2\) 为 Prüfer 转树：
#include<bits/stdc++.h>
const int N=5e6+5;
#define o(n) for(int i=1;i<n;++i)
int n,g[N],e[N],m,d[N],ct;
int main(){
std::cin>>n>>m;
if(m&1)o(n)std::cin>>g[i],d[g[i]]++;
else o(n-1)std::cin>>e[i],d[e[i]]++;
int p=n,l,f;
o(n+1)if(!d[i]){p=i;break;}l=p;
while(ct<n-2){
if(m&1)f=g[l],e[++ct]=f;else f=g[l]=e[++ct];
if(!--d[f]&&f<p)l=f;else {p++;while(d[p])++p;l=p;}
}
g[l]=n;o(n-(m&1))std::cout<<(m==1?e[i]:g[i])<<" ";
return 0;
}