Prufer 序列

# Prufer 序列 Prufer 序列是无根树的一种序列。对于一个 $n$ 个结点的树，Prufer 序列的长度为 $n-2$ 个，会用于解决一些有关树的计数问题。 先讲一讲 Prufer 序列是怎么得到的吧。 [P6086 【模板】Prufer 序列](https://www.luogu.com.cn/problem/P6086) 1. 每次找到树中入度为 $1$ 且编号最小的点。 2. 删去该节点并在序列中添加与该节点相邻的结点编号。 3. 重复上面的操作，知道剩下两个节点。 看张图，了解一下 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$ 为根节点，所以根本没必要存图。 好了还是开始将本题的正解吧。 我们使用指针来标记处理到目前为止叶子节点的最小编号，我们仍然像朴素算法一样自增查找，但在删除节点后，我们并没有必要跳回去啊。新产生的叶子节点无非存在两种情况： 1. 比指针小：由于指针是指向操作前的最小结点，比指针小说明它肯定是目前最小的叶子节点。直接进行处理即可 2. 比指针大：有可能不是目前最小的，不影响指针的正常操作，继续自增寻找即可。 ``` #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 序列的一些性质 1. 与一棵有标号的无根树对应 1. 某编号结点的入度为该点在prufer 序列中出现的次数 $+1$ 1. 点数为 $n$ 的有标号无根树个数为 $n^{n-2}$，有根树当然就 $\times n$ 就行啦。 1. 每个点度数为 $d_i$ 的有标号无根树个数为 $\frac{(n-2)!}{\prod\limits_{i=1}^n(d_i-1)!}$ 例题： [P2290 [HNOI2004]树的计数](https://www.luogu.com.cn/problem/P2290)