前言

因为 这道题 滚过来学 Prufer 了 /kel

Prufer序列

Prufer 序列是无根树的一种数列，可以将一个带标号的 \(n\) 点无根树用 \([1,n]\) 中的 \(n-2\) 个整数表示，即 \(n\) 点完全图的生成树与长度为 \(n-2\) 值域为 \([1,n]\) 的数列构成的双射。

一般用来解决一类树相关的计数问题。

从树到 Prufer

构造方式：

1. 每次选择一个编号最小的叶节点并删掉它，然后在序列中记录下它连接的那个节点。

2. 重复这个过程直到剩下两个节点。

直接做的时间复杂度是 \(\Omicron(n\log n)\) . 更优秀的做法：

指针指向编号最小的叶节点，如果删掉之后产生了新的节点且比指向的更小，那么就直接删。否则自增找到下一个编号最小的叶节点。

从 Prufer 到树

根据 Prufer序列 的性质，可以得到原树上每个点的度数。

一个度数为 \(d[i]\) 的点，在序列中出现的次数为 \(d[i]-1\) ，因为每次删去一个子节点都会在序列里面加入一次。

具体构造方式如下：

1. 初始时有一个 \(1\sim n\) 的序列和一个 \(n-2\) 个元素的 Prufer 序列。
2. 选择一个编号最小的度数为 \(1\) 的节点（也就是不在序列中的最小节点），与当前枚举到的 Prufer 序列的点相连，并在两个序列中分别删去这两个点。（显然，根据Prufer序列的构造过程逆推可得）
3. \(n-2\) 次之后剩下两个度数为 \(1\) 的点，将它们相连即可。

用类似的方式能够优化到 \(\Omicron(n)\) .

代码实现

【模板】Prufer 序列

//Author: RingweEH
const int N=5e6+10;
int n,opt,deg[N],fa[N],prufer[N];
ll ans=0;

void TreeToPrufer()
{
	memset( deg,0,sizeof(deg) );
	for ( int i=1; i<n; i++ )
		fa[i]=read(),deg[fa[i]]++;
	for ( int i=1,pos=1; i<=n-2; i++ )
	{
		while ( deg[pos] ) pos++;		//找一个编号最小的叶节点
		prufer[i]=fa[pos];		//将其父亲加入序列
		for ( ; i<=n-2; )
		{
			deg[prufer[i]]--;
			if ( deg[prufer[i]] ) break;	//减完之后不是叶
			if ( prufer[i]>=pos ) break;	//是叶节点但是编号在后面
			prufer[i+1]=fa[prufer[i]]; i++; 	//新产生的点加入序列
		}
		pos++;
	}
	for ( int i=1; i<=n-2; i++ )
		ans=ans^(1ll*i*prufer[i]);
	printf( "%lld\n",ans );
}

void PruferToTree()
{
	memset( deg,0,sizeof(deg) );
	for ( int i=1; i<=n-2; i++ )
		prufer[i]=read(),deg[prufer[i]]++;
	prufer[n-1]=n;
	for ( int i=1,pos=1; i<n; i++ )
	{
		while ( deg[pos] ) pos++; 	//自增找一个叶节点
		fa[pos]=prufer[i];	//与当前序列首相连
		for ( ; i<n-1; )
		{
			deg[prufer[i]]--;
			if ( deg[prufer[i]] ) break;
			if ( prufer[i]>=pos ) break;
			fa[prufer[i]]=prufer[i+1]; i++;
		}
		pos++;
	}
	for ( int i=1; i<n; i++ )
		ans=ans^(1ll*i*fa[i]);
	printf( "%lld\n",ans );
}

int main()
{
	n=read(); opt=read();
	if ( opt==1 ) TreeToPrufer();
	else PruferToTree();

    return 0;
}

凯莱公式(Cayley's Formula)

由于 \(n\) 点的 Prufer序列 有 \(n^{n-2}\) 种，根据双射的关系，有结论：

\(n\) 点带标号无根树有 \(n^{n-2}\) 种。

拓展：

设树上点 \(i\) 的度数为 \(d_i\) ，对应无根树数量为 \(\dfrac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}\) .（其实就是可重元素全排列，因为是双射嘛）

Generalized Cayley's Formula

结论：设 \(f(n,m)\) 为 \(n\) 个点组成 \(m\) 棵树，且 \(1\sim m\) 不在同一棵树中的方案数（有标号，无根），有

\[f(n,m)=mn^{n-m-1} \]

Cayley's Formula 是 \(m=1\) 的特例。

证明看这里

拓展

\(n\) 个带权点，边权为两两点权之积，树的权值为边权之积。对于所有 \(n\) 点带标号无根树，其树权总和为：

\[\left(\prod_{i=1}^n{val_i}\right)\left(\sum_{i=1}^nval_i\right)^{n-2} \]

习题

树的计数

一个有 \(n\) 个节点的树，设它的节点分别为 \(v_1,v_2,\ldots,v_n\) ，已知第 \(i\) 个节点 \(v_i\) 的度数为 \(d_i\) ，问满足这样的条件的不同的树有多少棵。

Solution

直接套 \(\dfrac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}\) 的公式。但是需要高精/质因数分解。

得知了某个奇怪的技巧：可以缩小选择范围，设之前已经枚举的 \(d_i-1\) 之和为 \(sum\) ，那么对于新的 \(d_i-1\) ，方案数只有 \(C(n-2-sum,d_i-1)\) 种，这样就不需要在计算上面做更多的处理，预处理组合数即可。

然后注意一些特判：

• \(n=1\) 的时候判一下度数
• \(\sum d_i=2*n-2\) ，所以 \(\sum d_i-1=n-2\) ，如果不相等说明不连通，如果中间有度数为 \(0\) 也是。

//Author: RingweEH
const int N=160;
int n,d[N];
ll C[N][N];

void C_init()
{
	for ( int i=0; i<=n; i++ )
	{
		C[i][0]=1;
		for ( int j=1; j<=i; j++ )
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
}

int main()
{
	n=read();
	if ( n==1 )
	{
		d[1]=read();
		if ( d[1]==0 ) printf( "1" );
		else printf( "0" );
		return 0;
	}

	C_init(); int sum=0;
	for ( int i=1; i<=n; i++ )
	{
		d[i]=read();
		if ( !d[i] ) { printf( "0" ); return 0; }
		d[i]--; sum+=d[i];
	}
	if ( sum^(n-2) ) { printf( "0" ); return 0; }
	sum=0; ll ans=1;
	for ( int i=1; i<=n; i++ )
		ans=ans*C[n-2-sum][d[i]],sum+=d[i];

	printf( "%lld\n",ans );

    return 0;
}

明明的烦恼

给出标号为 \(1\sim n\) 的点，以及最后某些（没有限定哪些）点的度数，任意连边，问有多少符合要求的树。

Solution

记没有限定的位置数量为 \(k\) .

根据Prufer序列，令 \(S=\sum d_i-1\) ，显然有：

\[\dfrac{(n-2)!}{\prod_{i=1}^n (d_i-1)!} \]

由于这 \(S\) 个位置任意选择，要乘上 \(C_{n-2}^S\) ；而剩下了 \(n-2-S\) 个位置，可以任意排布，所以还有 \((n-k)^{n-2-S}\) .

\[C_{n-2}^S\cdot\frac{S!}{\prod_{i=1}^k(d_i-1)!}*(n-k)^{n-2-s} \]

高精度就咕咕咕了

学习材料

Prufer codes与Generalized Cayley's Formula学习笔记