prufer序列学习笔记

定义

构造方法：每次删掉一个叶节点，将其父节点加入序列中。一共删n-2次，这样可以保证不重复。

性质

1. prufer序列与无根树一一对应
2. 度数为\(d_i\)的节点在序列中出现\(d_i-1\)次
3. n个节点完全图的生成树个数为\(n^{n-2}\)
4. 对于一颗无根树，度数序列给出，生成树个数为\(\frac{(n-2)!}{\prod(d_i-1)!}\)

例题

HNOI2004 树的计数

裸题。高精很恶心QAQ

n=(int)(input())
if n==1:
    x=(int)(input());
    if x==0:print(1);
    else:print(0);
    exit();
g=[0 for i in range(n+200)];
g[0]=1;
for i in range(1,n):g[i]=g[i-1]*i;
ans=g[n-2];tot=0;s=input().split();
for i in range(n):
    x=(int)(s[i]);
    if x==0:print(0);exit();
    tot+=x-1;ans//=g[x-1];
if(tot==n-2):print(ans);
else:print(0);

HNOI2008 明明的烦恼

同样是裸题。把没有d的分配一下然后组合数算一下就好了。不想写高精度。

BZOJ4766

完全二分图的生成树计数

考虑构造prufer序列的方法，删掉某个点后加入与其相连的父节点，则加入的点一定在二分图的另一边。那么考虑删去了那些点，显然最后留下来的是两个相连的点，即两边各一，则左边删除n-1个，右边删除m-1个，prufer序列里添加数量的相反。

最开始我以为方案数是\(n^{m-1}m^{n-1}{n+m-2\choose {n-1}}\)，其实不然。发现删除一定是有顺序的，即左边-右边这样重复删。

还有一种方法是直接上矩阵生成树定理，手算一下/找规律。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll read(){
	ll x=0,pos=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return pos?x:-x;
} 
ll n,m,p;
ll mul(ll a,ll b){
	ll res=0;
	while(b){
		if(b&1) res=(res+a)%p;
		a=a*2ll%p;b>>=1;
	}
	return res;
}
ll ksm(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=mul(res,a);
		a=mul(a,a);b>>=1;
	}
	return res;
}
int main(){
	n=read(),m=read(),p=read();
	printf("%lld",mul(ksm(n,m-1),ksm(m,n-1)));
	return 0;
}