【学习笔记】Prüfer 序列

定义

Prüfer 序列能够将一个有

n

个节点的树用

[1,n]

中的

n-2

个元素表示，每一个 Prüfer 序列对应唯一一颗树，每一颗树对应唯一一个 Prüfer 序列。

如何对于一棵树建立它的 Prüfer 序列？每次选择该树最小的叶子结点并删掉它，然后在序列的末尾把它所连接的节点加入，知道只剩

2

个节点，此时 Prüfer 序列中有

n-2

个元素。

实现

首先考虑暴力实现，显然有一个

O(n^2)

的算法可以实现，具体的，枚举最小的没被删除的叶子结点并删除。

然后考虑优化，不难发现用堆即可优化到

O(n\log n)

。

但是，Prüfer 序列是可以线性构造的，具体流程如下：

维护一个指针 $p$ ，初始时 $p$ 指向编号最小的叶子结点，同时我们维护每个节点的出度 $cnt$ 以及每个节点的父亲，每次删除一个节点 $u$ 时，将它的父亲 $fa$ 加入到序列中，同时 $cnt_{fa}=cnt_{fa}-1$ ，然后判断若 $cnt_{fa}=0$ 且 $fa<u$ 则 $u=fa$ 然后继续，否则就 $u$ 递加，可以证明此方法正确。

不难发现编号最大的节点一定不会被删除，因为一个点数多于

2

的树必然不止一个叶子结点。故我们在对一棵无根树建立 Prüfer 序列时可以将最大的节点作为根。

解决的问题

Prüfer 序列可以解决许多与生成树计数有关的题目，每有一个 Prüfer 序列就有一种生成树的方案。

例题

【模板】Prufer 序列

板子，按照上面的线性建 Prüfer 序列的方法即可，但是还需要将 Prüfer 序列转化为树，方法其实与建立 Prüfer 序列差不多，故不在赘述。

由于题目说以

n

为根，所以可以不用建树。

代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int fa[N],cnt[N],p[N];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,op;
	cin>>n>>op;
	long long ans=0;
	if(op==1)
	{
		for(int i=1;i<n;i++)cin>>fa[i],cnt[fa[i]]++;
		for(int i=1,j=1;i<=n-2;i++,j++)
		{
			while(cnt[j]!=0)j++;
			p[i]=fa[j];
			while(i<n-2&&--cnt[p[i]]==0&&p[i]<j)p[i+1]=fa[p[i]],i++;
		}
		for(int i=1;i<=n-2;i++)ans^=1ll*i*p[i];
	}
	else
	{
		for(int i=1;i<=n-2;i++)cin>>p[i],cnt[p[i]]++;
		p[n-1]=n;
		for(int i=1,j=1;i<n;i++,j++)
		{
			while(cnt[j]!=0)j++;
			fa[j]=p[i];
			while(i<n-1&&--cnt[p[i]]==0&&p[i]<j)fa[p[i]]=p[i+1],i++;
		}
		for(int i=1;i<n;i++)ans^=1ll*i*fa[i];
	}
	cout<<ans;
	return 0;
}

[HNOI2004] 树的计数

根据 Prüfer 序列的性质，每个 Prüfer 序列对应一种生成树的方案，故考虑有几种 Prüfer 序列。

题目给定每个节点的度数，即规定了每个节点在 Prüfer 序列出现的次数，算个多重组合数即为答案。设答案为

ans

，则有：

ans=\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}

上式中

n-2

为 Prüfer 序列的长度，

d_i-1

为每个节点出现的个数。

需要注意的是，会出现无解的情况，所有情况如下：

$\sum_{i=1}^nd_i\ne2(n-2)$ ，即度数对应的边的数量不符合一棵树的边的数量。
$n\ne 1$ 且 $\sum_{i=1}^n[d_i=1]<2$ ，即少于 $2$ 个叶子结点（节点数不为 $1$ 的无根树最少有 $2$ 个叶子结点）。
$n=1$ 且 $d_1\ne 0$ ，只有一个节点且该节点的度数不为 $0$ 。

代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int cnt[N];
void solve(int n,int val)
{
	for(int i=1;i<=n;i++)
	{
		int tmp=i;
		for(int j=2;j*j<=tmp;j++)
			while(tmp%j==0)cnt[j]+=val,tmp/=j;
		if(tmp>1)cnt[tmp]+=val;
	}
}
int a[N];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,sum=0,c=0;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i],c+=(a[i]==1?1:0);
	if(sum!=2*(n-1)||n!=1&&c<2||n==1&&a[1]!=0)
	{
		cout<<0;
		return 0;
	}
	solve(n-2,1);
	for(int i=1;i<=n;i++)solve(a[i]-1,-1);
	long long ans=1;
	for(int i=1;i<=150;i++)
	for(int j=1;j<=cnt[i];j++)
		ans*=i;
	cout<<ans;
	return 0;
}

【学习笔记】Prüfer 序列

文章操作

定义

实现

解决的问题

例题

【模板】Prufer 序列

[HNOI2004] 树的计数

相关推荐

评论

【学习笔记】Prüfer 序列