Prufer 序列可以將一個(gè)帶標(biāo)號(hào) n 個(gè)結(jié)點(diǎn)的樹(shù)用[1,n]中的 n-2 個(gè)整數(shù)表示。你也可以把它理解為完全圖的生成樹(shù)與數(shù)列之間的雙射。

顯然你不會(huì)想不開(kāi)拿這玩意兒去維護(hù)樹(shù)結(jié)構(gòu)。這玩意兒常用組合計(jì)數(shù)問(wèn)題上。

Heinz Prufer 于1918年發(fā)明這個(gè)序列來(lái)證明凱萊定理。

1. Prufer是什么？

把一個(gè)無(wú)根樹(shù)變成一個(gè)序列，也可以把一個(gè)序列變成一個(gè)序列

2. 性質(zhì)

（1）prufer序列與無(wú)根樹(shù)一一對(duì)應(yīng)；

（2）度數(shù)為的結(jié)點(diǎn)會(huì)在 prufer 序列中出現(xiàn)次；

（3）一個(gè) n 個(gè)結(jié)點(diǎn)的無(wú)向完全圖的生成樹(shù)的個(gè)數(shù)(Cayley公式)。

3. 轉(zhuǎn)化過(guò)程

把無(wú)根樹(shù)變成序列；

         6

        /

       5    

      / \

     4   2

    /

   3

  /

 1

 每次看度數(shù)=1的葉子節(jié)點(diǎn)中刪除后總數(shù)變化最小的點(diǎn)；

 刪去1變化最小,輸出刪除1前1的父節(jié)點(diǎn)3；

         6

        /

       5    

      / \

     4   2

    /

   3

 刪去2變化最小，輸出刪除2前2的父節(jié)點(diǎn)5；

         6

        /

       5    

      / 

     4  

    /

   3 

 刪去3變化最小，輸出4；

         6

        /

       5    

      / 

     4  

 刪去4變化最小，輸出5；

         6

        /

       5   

 剩下兩個(gè)點(diǎn)后，一定刪除非最大的數(shù)，最后剩下的一個(gè)點(diǎn)一定是輸出最大的n號(hào)點(diǎn) 6；

         6

        /

       5    

4. 原理

從小到大枚舉 j (編號(hào)最小的度數(shù)=1的葉子節(jié)點(diǎn))，把 j 刪掉后最多產(chǎn)生一個(gè)新的葉子節(jié)點(diǎn)

情況1：刪葉子節(jié)點(diǎn)后，新多出來(lái)的點(diǎn) k 比 j 大，不用管，j 會(huì)從小到大枚舉，遲早會(huì)枚舉到這個(gè)點(diǎn)k；

情況2：刪葉子節(jié)點(diǎn)后，新多出來(lái)的點(diǎn)比 j 小，說(shuō)明 k 就是當(dāng)前最小葉子節(jié)點(diǎn)。

代碼實(shí)現(xiàn)

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