介绍
(prufer)序列是一个比较实用但好像有点冷门的东西。可以用来解决有关度数的树上计数问题，与无根树紧密相连。
树上计数套这个太好用啦(≧▽≦)/啦啦啦
相关操作
从无根树到prufer序列
重复以下操作：
1.找到度数为(1)且编号最小的点。
2.把它的父亲节点加入(prufer)序列中。
3.删去这个点。
直到树上只剩两个点为止。
简单来说，就是找叶子，加父亲，剥叶子的过程
从prufer序列到无根树
重复以下过程
1.取出(prufer)序列中最前面的元素(u)
2.取出点集中没有在(prufer)序列中出现过且编号最小的点(v)
3.连边(u,v)
4.分别删除(u,v)
直到在点集中只剩下两个点，给它们连边。
以上操作可以用优先队列维护
一些性质
性质一
(prufer)序列中编号对应的出现次数为这个节点的度数-1。
好理解吧，儿子们在删除时就会把它加进序列，一个点有（度数-1）个儿子，还有一个度数留给父亲。
性质二
(prufer)序列与无根树一一对应。
(prufer)序列的长度为点数-2。
性质三
(n)个无区别点的无向完全图的生成树计数为(n^{n-2})个
或者说，有(n)个点，他们可以形成形状不同的树的个数为(n^{n-2})
形状不同：邻接矩阵不同
(Why?)既然是任意生成树，那(prufer)序列中每个位置都有可能是([1-n]) ，序列长度为(n-2)
性质四
(n)个有区别的点，组成的无根树个数为(n*n^{n-2})=(n^{n-1})
性质五
已知各个节点的度数(d_i)，能形成的不同的无根树的个数为
一些题目
LouguP6806 Prufer序列
模板题
有趣的指针写法。
Code
#include<bits/stdc++.h>
#define N (5000010)
#define ll long long
using namespace std;
int n,m,d[N],fa[N],pf[N];
ll ans;
inline int read(){
int w=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w;
}
int main(){
n=read(),m=read();
//用指针的方式省去一个log
if(m==1){
for(int i=1;i<n;i++) d[fa[i]=read()]++;
//d[i]:儿子的个数
for(int i=1,j=1;i<=n-2;i++,j++){
while(d[j]) j++;
//还有儿子，不能选
pf[i]=fa[j];
//找到了编号最小的没有儿子的
while(i<=n-2&&!--d[pf[i]]&&pf[i]<j) pf[i+1]=fa[pf[i]],i++;
//pf[i]变成叶子了而且编号比之前的j小
}
for(int i=1;i<=n-2;i++) ans^=(ll)i*pf[i];
printf("%lld
",ans);
}
else{
//反的操作
for(int i=1;i<=n-2;i++) pf[i]=read(),d[pf[i]]++;
pf[n-1]=n;
for(int i=1,j=1;i<n;i++,j++){
while(d[j]) j++;
fa[j]=pf[i];
while(i<n&&!--d[pf[i]]&&pf[i]<j) fa[pf[i]]=pf[i+1],i++;
}
for(int i=1;i<n;i++) ans^=(ll)i*fa[i];
printf("%lld
",ans);
}
return 0;
}
[HNOI2004]树的计数
性质五，直接算。
Code
#include<bits/stdc++.h>
#define ll long long
#define N (161)
using namespace std;
ll n,sum,ans=1,a[N],f[N];
bool flag1;
inline ll read(){
ll w=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w;
}
inline ll fc(ll x){
ll res=1;
for(ll i=2;i<=x;i++) res*=i;
return res;
}
int main(){
n=read();
for(ll i=1;i<=n;i++){
a[i]=read();
sum+=a[i]-1;
if(a[i]>n-1||(!a[i]&&n!=1)) flag1=1;
f[i]=fc(a[i]-1);
}
if(flag1||sum!=n-2){
puts("0");
return 0;
}
ll j=1;
for(ll i=1;i<n-1;i++){
ans=ans*i;
if(j>n) continue;
if(!(ans%f[j])) ans/=f[j++];
}
printf("%llu
",ans);
return 0;
}
[HNOI2008]明明的烦恼
题意简述
(n)个点，其中一些点的度数确定，求生成树的个数。
Sol
这回没有公式直接套了。
设：
(sum)为所有确定度数的点的(d_i-1)之和
(cnt)为确定度数的点的个数
那我们首先用性质五把这一部分的贡献算了
组合数的意义是在(prufer)序列中共有(n-2)个位置，这些确定度数的点可以在其中随便放。
那没确定度数的点呢?
意思是(prufer)序列剩下了(n-2-sum)个位置，剩下的点随便放。
(ans=ans_1*ans_2)
(ans=frac{sum!}{prodlimits_{i=1}^n(d_i-1)}*dbinom{n-2}{sum}*(n-cnt)^{n-2-sum})
(ans=frac{sum!}{prodlimits_{i=1}^n(d_i-1)}*frac{(n-2)!}{sum!*(n-2-sum)!}*(n-cnt)^{n-2-sum})
(ans=frac{(n-2)!*(n-cnt)^{n-2-sum}}{prodlimits_{i=1}^n(d_i-1)*(n-2-sum)!})
要高精，这里是质因数分解+简单的高精乘
Code
#include<bits/stdc++.h>
#define N (1010)
#define M (1000010)
#define ll long long
using namespace std;
ll n,cp,sum,cnt,d[N],p[N],res[N],ans[M];
bool used[N];
inline ll read(){
ll w=0;
char ch=getchar();
bool f=0;
while(ch>'9'||ch<'0'){
if(ch=='-') f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return f?-w:w;
}
inline void oula(){
for(int i=2;i<=1000;i++){
if(!used[i]) p[++cp]=i;
for(int j=1;j<=cp;j++){
if(i*p[j]>1000) break;
used[i*p[j]]=1;
if(!(i%p[j])) break;
}
}
return;
}
inline void calc(ll num,ll v){
for(int i=1;i<=cp;i++)
while(num%p[i]==0)
num/=p[i],res[i]+=v;
return;
}
inline void mul(ll x){
for(int i=1;i<=ans[0];i++) ans[i]*=x;
for(int i=1;i<=ans[0];i++){
if(ans[i]>=10){
ans[i+1]+=ans[i]/10,ans[i]%=10;
if(i==ans[0]) ans[0]++;
}
}
return;
}
int main(){
oula();
n=read();
bool flag1=0;
for(int i=1;i<=n;i++){
d[i]=read();
if(d[i]!=-1) cnt++,sum+=d[i]-1;
if(!d[i]) flag1=1;
}
if(sum>n-2||flag1){
puts("0");
return 0;
}
ll left=n-2-sum;
for(ll i=1;i<=left;i++) calc(i,-1);
for(ll i=1;i<=left;i++) calc(n-cnt,1);
for(ll i=1;i<=n-2;i++) calc(i,1);
for(ll i=1;i<=n;i++)
if(d[i]!=-1)
for(ll j=2;j<d[i];j++) calc(j,-1);
ans[0]=ans[1]=1;
for(int i=1;i<=cp;i++)
while(res[i]) mul(p[i]),res[i]--;
for(int i=ans[0];i>=1;i--) printf("%lld",ans[i]);
puts("");
return 0;
}