prufer 序
$prufer$ 序列可以将一个带标号 $n$ 个结点的树用 $[1,n]$ 中的 $n-2$ 个整数表示。或者可以说，一个 $prufer$ 序对应一个无根树。
$prufer$ 构造方式：每回将编号最小的叶节点删掉，记录连接它的唯一节点，最后就剩两个节点就结束操作。得到的记录的数列就是 $prufer$ 序列。一个简单的图示：
我们根据它的构造原理，很简单就能搞明白为什么会有唯一对应关系。
$prufer$ 序列的性质：
在构造完 $prufer$ 序列后原树中会剩下两个结点，其中一个一定是编号最大的点 。
每个结点在序列中出现的次数是其度数减 $1$。（没有出现的就是叶结点）
思路
在这到题目中，规定了根节点 $n$，这样，在父节点确定时，$prufer$ 序是唯一的，我们已经知道了每个点的父节点，或者 $prufer$ 序，即让我们无根树和 $prufer$ 序相互转换。由于结果已经知道是唯一的，所以只要知道构造方法就可以得出结果。
互相转换的关键在于，$pruerl$ 构造原理：每回都是将最小节点除去，记录它的唯一连接节点。
细节就看代码吧。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e7+10;
int n;
int f_f[o_o];//父数组
int p_p[o_o];//prufer 序
int s_s[o_o];//统计节点出现的次数
long long a_s;
void f_p(){//有根树转 prufer 序列
for(int i=1;i<n;i++){
f_f[i]=r_r();//读入序列
++s_s[f_f[i]];//（父）节点的度加 1
}
for(int i=1,j=1;i<=n-2;i++,j++){
while(s_s[j])++j;//找编号最小的节点
p_p[i]=f_f[j];//加入 prufer 序列
while(i<=n-2&&!--s_s[p_p[i]]&&p_p[i]<j){
p_p[i+1]=f_f[p_p[i]];//父节点小，加入 prufer 序列。
++i;
}
}
for(int i=1;i<=n-2;i++)a_s^=1ll*i*p_p[i];//统计权值
}
void s_p(){//prufer 序列转有根树
for(int i=1;i<=n-2;i++){
p_p[i]=r_r();//读入序列
++s_s[p_p[i]];//（父）节点深度加一
}
p_p[n-1]=n;//题目中说读入将 n 设为根，最后一定的 prufer 一定是 n。
for(int i=1,j=1;i<n;i++,j++){
while(s_s[j])++j;//找编号最小的节点
f_f[j]=p_p[i];//加入父序列
while(i<n&&!--s_s[p_p[i]]&&p_p[i]<j){
f_f[p_p[i]]=p_p[i+1];//父节点小，加入父序列
++i;
}
}
for(int i=1;i<n;i++)a_s^=1ll*i*f_f[i];//统计权值
}
int main(){
n=r_r();//读入树的点数
int op=r_r();//转化类型
if(op==1)f_p();//父亲序列
else s_p();//prufer 序列
printf("%lld",a_s);//输出结果
return 0;
}补充
- 如果题目中没有规定 $n$ 为根节点，也没有规定父子节点关系，有多少种 $prufer$ 序？
这就是 $Cayley$ 公式。
若该完全图有 $n$ 个节点，则任意一个长度为 $n-2$ 的 $prufer$ 序列都可以重构出其一棵生成树，且各不相同。又因为 $prufer$ 序列的值域在 $[1,n]$ ，所以总共有 $n^{n-2}$ 种情况。
- 有 $n$ 个点，能组成多少个有根树？
和无根树不同出在于根节点不同，一共有 $n\times n^{n-2}=n^{n-1}$ 种情况。
我们知道每个点的度数和在 $prufer$ 序中出现的次数关系有关：
- 给定 $n$ 个点，每个点的度数为 $d_i$，无根树有多少种？
因为 $prefur$ 序的长度 $n-2$ 则有 $(n-2)!$ 中排法，其中每个点又会出现重复的贡献 $(d_i-1)!$ 次。
所以最后一共有：
种结果。
