引入
一个小知识,稍微学一下
其实 prufer 序列就是一种将带标号的树用一个唯一的整数序列表示的方法.
(小知识 prüfer 是德语,所以应该读作/代码里应该写作 pruefer)
定义
每次选择一个编号最小的叶结点并删掉它,然后在序列中记录下它连接到的那个结点。重复 \(n-2\) 次后就只剩下两个结点
終わった!很简单的啦(
小性质
- 是一个双射(一一对应)
- 在构造完 prufer 序列后原树中会剩下两个结点,其中一个一定是编号最大的点
- 每个结点在序列中出现的次数是其度数减 \(1\)(没有出现的就是叶结点)
代码
代码也很好实现(看代码就看得懂吧,反正博客是给自己看的(bushi)(代码的题目链接)
这个是 \(O(n\log n)\) 的做法,有 \(O(n)\) 的做法,可惜我不会.
int n,m;
int fa[N],pf[N],deg[N];
void t_to_p() //父亲序列转 prufer 序列
{
int cnt=0;
for(int i=1; i<n; i++) deg[fa[i]]++; //记录节点的度
priority_queue<int, vector<int>, greater<int> > q; //用堆维护
for(int i=1; i<=n; i++) if(deg[i]==0) q.push(i);
while(!q.empty())
{
int u=q.top(); q.pop();
pf[++cnt]=fa[u]; deg[fa[u]]--; if(deg[fa[u]]==0) q.push(fa[u]);
} //每次把编号最小的叶子结点取出来,更新prufer序列,然后如果原来的父亲成为叶子,再加进去
}
void p_to_t() // prufer 序列转父亲序列
{
for(int i=1; i<=n; i++) deg[i]=1;
for(int i=1; i<=n-2; i++) deg[pf[i]]++; //根据性质,可以求出节点的度
priority_queue<int, vector<int>, greater<int> > q; //用堆维护
for(int i=1; i<=n; i++) if(deg[i]==1) q.push(i);
int t=1; pf[n-1]=n;
while(!q.empty())
{
int u=q.top(); q.pop();
fa[u]=pf[t],t++;
deg[u]--,deg[fa[u]]--;
if(deg[fa[u]]==1) q.push(fa[u]);
} //每次取出编号最小的度数为1的点,然后连向它的父亲(
}
小应用
例子1
完全图生成树个数(无标号)(Cayley 公式)
\(n\) 个点,prufer 序列有 \(n^{n-2}\) 种,所以生成树个数也是这个.
完全图生成树个数(有标号)
\(n^{n-2}\cdot n!\) (不然呢?不就是加个顺序
例子2
一个有 \(n\) 个节点的树,设它的节点分别为 \(v_1,v_2,\cdots,v_n\) ,已知第 \(i\) 个节点 \(v_i\) 的度数为 \(d_i\),问满足这样的条件的不同的树有多少棵.
题解:prufer序列中,每个节点出现的次数是 \(d_i-1\),所以其实就是一个可重集排列,答案为 \(\displaystyle\frac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}\)
有一些特判,\(n=1\) 的时候要特判,有度数为零的要特判,度数加起来不等于 \(2n-2\) 要特判
标签:度数,结点,int,特判,笔记,序列,prufer From: https://www.cnblogs.com/copper-carbonate/p/16974272.html