Prufer 序列可以将一个带标号 n 个结点的树用[1,n]中的 n-2 个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。
显然你不会想不开拿这玩意儿去维护树结构。这玩意儿常用组合计数问题上。
Heinz Prufer 于1918年发明这个序列来证明凯莱定理。
1. Prufer是什么？
把一个无根树变成一个序列，也可以把一个序列变成一个序列
2. 性质
（1）prufer序列与无根树一一对应；
（2）度数为
的结点会在 prufer 序列中出现
次；
（3）一个 n 个结点的无向完全图的生成树的个数
(Cayley公式)。
3. 转化过程
把无根树变成序列；
6
/
5
/ \
4 2
/
3
/
1
每次看度数=1的叶子节点中删除后总数变化最小的点；
删去1变化最小,输出删除1前1的父节点3；
6
/
5
/ \
4 2
/
3
删去2变化最小，输出删除2前2的父节点5；
6
/
5
/
4
/
3
删去3变化最小，输出4；
6
/
5
/
4
删去4变化最小，输出5；
6
/
5
剩下两个点后，一定删除非最大的数，最后剩下的一个点一定是输出最大的n号点 6；
6
/
5
4. 原理
从小到大枚举 j (编号最小的度数=1的叶子节点)，把 j 删掉后最多产生一个新的叶子节点
情况1：删叶子节点后，新多出来的点 k 比 j 大，不用管，j 会从小到大枚举，迟早会枚举到这个点k；
情况2：删叶子节点后，新多出来的点比 j 小，说明 k 就是当前最小叶子节点。
代码实现
#include<bits/stdc++.h>
#define int long long
#define rint register int
#define endl '\n'
using namespace std;
const int N = 5e6 + 5;
int n,m,f[N],d[N],p[N];
int inline tree2prufer(){
for(rint i=1;i<n;i++) cin>>f[i],d[f[i]]++;
for(rint i=1,j=1;i<n-1;j++){
while(d[j]){
j++;
}
p[i++]=f[j];
while(i<n-1&&--d[p[i-1]]==0&&p[i-1]<j){
p[i++]=f[p[i-1]];
}
}
int ans=0;
for(rint i=1;i<n-1;i++)
ans=ans^(1ll*i*p[i]);
return ans;
}
int inline prufer2tree(){
for(rint i=1;i<=n-2;i++) cin>>p[i],d[p[i]]++;
p[n-1]=n;
for(rint i=1,j=1;i<n;i++,j++){
while(d[j]){
j++;
}
f[j]=p[i];
while(i<n-1&&--d[p[i]]==0&&p[i]<j){
f[p[i]]=p[i+1];
i++;
}
}
int ans=0;
for(rint i=1;i<=n-1;i++)
ans=ans^(1ll*i*f[i]);
return ans;
}
signed main(){
cin>>n>>m;
int res;
if(m==1)
res=tree2prufer();
else
res=prufer2tree();
cout<<res<<endl;
return 0;
}C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程