Prufer序列

Prufer 序列

作用

将带标号 (n) 节点树用 (n-2) 个 ([1,n]) 的整数表示，

即 (n) 个点的完全图的生成树和长度为 (n-2) 的值域为 ([1,n]) 的数列构成的双射。

Cayley 定理，(n) 个点有标号生成树共 (n^{n-2}) 个。Anne's game

算法

树转 Prufer 序列

每次选择一个编号最小的叶节点删除，记录它的父亲。

重复 (n-2) 次以后剩下两个节点，算法结束。

堆：(O(nlog n))

指针：(O(n))

指针指向编号最小的叶节点，每次删掉以后，

• 如果产生了新的叶节点，且编号比已经填写完的更小，就直接继续删掉

• 否则++，找到下一个编号最小的叶节点。

Prufer 序列转树

可以得到原树上每个点的度数。

每次选择一个编号最小的度数为1的节点，与当前枚举的Prufer序列的点连接，然后同时减掉两个点的度数，重复 (n-2) 次后剩下两个度数为1的点，其中一个是 (n) ，连接他们即可。

堆： (O(nlog n))

指针：(O(n))

具体而言，指针指向编号最小的度数为 1 的节点。

每次将它与当前枚举到的 Prufer 序列的点连接之后，

• 如果产生了新的度数为 1 的节点且编号比当前处理“完”的更小，则直接继续将它与下一个 Prufer 序列的点连接，
• 否则++，找到下一个编号最小的度数为 1 的节点。

实现

【模板】Prufer 序列

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6+10;
int n,tp,f[N],p[N],d[N];
ll ans=0;
void Tree_Prufer(){
    for(int i=1;i<=n-1;i++) scanf("%d",&f[i]),d[f[i]]++;
    for(int i=1,j=1;i<=n-2;i++,j++){
        while(d[j]) j++; p[i]=f[j];
        while(i<=n-2&&!--d[p[i]]&&p[i]<j)
            p[i+1]=f[p[i]],i++;
    }
    for(int i=1;i<=n-2;i++) ans^=1ll*i*p[i];
}
void Prufer_Tree(){
    for(int i=1;i<=n-2;i++) scanf("%d",&p[i]),d[p[i]]++; p[n-1]=n;
    for(int i=1,j=1;i<n;i++,j++){
        while(d[j]) j++; f[j]=p[i];
        while(i<n&&!--d[p[i]]&&p[i]<j)
            f[p[i]]=p[i+1],i++;
    }
    for(int i=1;i<n;i++) ans^=1ll*i*f[i];
}
int main(){
    scanf("%d%d",&n,&tp);
    (tp==1)?Tree_Prufer():Prufer_Tree();
    printf("%lld
",ans);
    return 0;
}