Prufer 序列

hekaiyu · 2020-05-23 23:17:19 · 题解

Prufer 序列

Prufer 序列是无根树的一种序列。对于一个 n 个结点的树，Prufer 序列的长度为 n-2 个，会用于解决一些有关树的计数问题。

先讲一讲 Prufer 序列是怎么得到的吧。

P6086 【模板】Prufer 序列

每次找到树中入度为 1 且编号最小的点。
删去该节点并在序列中添加与该节点相邻的结点编号。
重复上面的操作，知道剩下两个节点。

看张图，了解一下 Prufer 序列的生成过程，（样例一为例）。

朴素算法

建图
暴力枚举寻找入度为 1 且编号最小的点。

添加与该节点相邻的结点编号

long long make_prufer(int n,int *d,int *p){
for(int i=1;i<n;++i){
    int a;a=read();
    cc(i,a);cc(a,i);//建图
    ++d[a];++d[i]; 
}
int head=0;
for(int i=1;i<=n-2;++i){
    while(d[++head]!=1);//寻找节点
    for(int j=ves[head];j;j=st[j].next){
        if(!d[st[j].v])continue;
        p[i]=st[j].v;
        --d[st[j].v];
        --d[head];//处理完后删点
        if(d[st[j].v]==1&&head>st[j].v)head=st[j].v-1;//发现更小结点跳回去
    }
}
long long ans=0;
for(int i=1;i<=n-2;++i)ans=(long long)((long long)i*p[i])^ans;//答案统计
return ans;
}
//转树的方法类似
long long make_fa(int n,int *d,int *fa){
for(int i=1;i<=n-2;i++){
    prufer[i]=read();
    ++d[prufer[i]];
}
prufer[n-1]=n;
int head=1,top=n-2;
for(int i=1;i<=n-1;++i){
    while(d[head]!=0)++head;//寻找最小结点
    fa[head]=prufer[i];
    --d[prufer[i]];
    --d[head];
    if(d[prufer[i]]==0&&prufer[i]<head)head=prufer[i];
}
long long ans=0;
for(int i=1;i<=n-1;++i)ans=(long long)((long long)i*fa[i])^ans;
return ans;
}

显然上述的方法时间复杂度 O(n^2) 。预计得分 20 分（实际 60 分）。

虽然办法很傻但起码让人了解了定义。

堆优化

显然上面的代码一步一步寻找结点的效率很低。其实只需要将每次操作后入度为一的点扔到兑礼即可时间复杂度 O(n \log n)，预期得分 60 分。

代码类似就不贴了。

再优化----时间复杂度 O(n)

考虑到一棵树最少有两个叶子结点，所以点数为 n 的点一定会留到最后，题目中恰好以 n 为根节点，所以根本没必要存图。

好了还是开始将本题的正解吧。

我们使用指针来标记处理到目前为止叶子节点的最小编号，我们仍然像朴素算法一样自增查找，但在删除节点后，我们并没有必要跳回去啊。新产生的叶子节点无非存在两种情况：

比指针小：由于指针是指向操作前的最小结点，比指针小说明它肯定是目前最小的叶子节点。直接进行处理即可

比指针大：有可能不是目前最小的，不影响指针的正常操作，继续自增寻找即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5000005;
int read(){//快读
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
    if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
    res=res*10+c-48;
return res*f;
}
int n,type;
int f[maxn],d[maxn],topss[maxn],x[maxn],top,maxv[maxn],p[maxn];
long long make_prufer(int n){
int headss=n;long long ans=0;
for(int i=1;i<n;++i)f[i]=read(),++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;//代替朴素算法中的if
}
for(int i=1;i<=n-2;++i)ans^=(long long)i*p[i];
return ans;
}
long long make_fa(int n){
long long ans=0;
for(int i=1;i<=n-2;++i)p[i]=read(),++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^=(long long)i*f[i];
return ans;
}
int main(){
n=read(),type=read();
if(type==1)printf("%lld",make_prufer(n));
if(type==2)printf("%lld",make_fa(n));
return 0;
}

提供一种倒序求解 fa 的方法（掠过吧），直接注释在代码里好了。

long long make_fa(int n){
for(int i=1;i<=n-2;++i)p[i]=read(),++d[p[i]];
int head=n-2,top=n;long long ans=(long long)n*p[n-2];//特殊处理开头两个点
x[p[n-2]]=1,x[n]=1;//x表示是否已经处理
while(head){
    if(d[p[head-1]]&&!x[p[head-1]]){//枚举prufer[head]，如果该点没有在树里，那么在这个位置必须添加。
        x[p[head-1]]=1;
        ans=(long long)((long long)p[head-1]*p[head])^ans;//由prufer[head-1]指向prufer[head]
        --head;
        continue;
    }
    while(x[top]&&top)--top;//当前处理到的点
    x[top]=1; //之前是去掉最小的结点，所以贪心去寻找最小结点与prufer[head]连边。
    ans=(long long)((long long)top*p[head])^ans;
    --head;//枚举下一个点
}
return ans;
}

时间复杂度也是 O(n) （常数会大一点点吧）。

prufer 序列的一些性质

与一棵有标号的无根树对应
某编号结点的入度为该点在prufer 序列中出现的次数 +1
点数为 n 的有标号无根树个数为 n^{n-2}，有根树当然就 \times n 就行啦。
每个点度数为 d_i 的有标号无根树个数为 \frac{(n-2)!}{\prod\limits_{i=1}^n(d_i-1)!}

例题： P2290 [HNOI2004]树的计数