什么是Prufer序列？

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;
}