Prufer数列是无根树的一种数列,对于一棵确定的无根树,有唯一与之对应的prufer数列(一一对应)

  1. 无根树转prufer序列
    (1)找到编号最小的度数为1的点

(2)删除该节点并在该序列中添加与该节点相连的节点的编号
(3)重复1,2操作,直到整棵树只剩下两个节点

  1. prufer序列转化为无根树
    (1)每次取出prufer序列中最前面的元素u

(2)在点集中找到编号最小的没有在点集中出现的元素v
(3)给u,v连边然后分别删除
(4)最后在点集中剩下两个节点,给它们连边(注意这里的点集是指作为v出现的点集
比如prufer数列:1 3 3 5的连边顺序就该是:
1-2
3-1
3-4
5-3
5-6

上面两种操作都可以用set维护,时间复杂度$O(nlogn)$ (重载一下运算符就好了叭

很多时候无根树问题可以转化为prufer数列来求解 (解决树的计数类问题

  1. 性质
    (1)prufer序列中某个编号出现的次数就等于这个编号的节点在无根树中的度数-1

(2)n个点的无向完全图的生成树的计数:$n^{n-2}$,即n个点的有标号无根树的计数
这里因为无根树与prufer序列一一对应,所以相当于枚举prufer序列每位选什么
(3)n个节点的度数依次为$d_1,d_2,....,d_n$的无根树共有$\frac{(n-2)!}{ sum_{i=1}^n(d_i-1)!}$个,因为prufer编码中数字i恰好出现$d_i-1$次
(4)n个点的有标号有根树的计数:
多乘一个根的选定n 2333:$n^{(n-2)}*n = n^{(n-1)}$

例题bzoj 1211 HNOI2004 树的计数

详见性质(3) 23333

code:

#include<bits/stdc++.h>
#define maxn 155
typedef long long ll;
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,d[maxn];
ll jc[maxn];
void init(){
    n=read();
    for(int i=1;i<=n;i++) d[i]=read();
    jc[0]=1;
    for(ll i=1;i<=n;i++) jc[i]=jc[i-1]*i;
    ll ans=jc[n-2];
    for(int i=1;i<=n;i++) ans/=jc[d[i]-1];
    printf("%lld",ans);
}
int main(){
    init();
    
    return 0;
}

但是有sb坑点,注意特判,这里就不再去改了23333

Last modification:March 21st, 2019 at 03:53 pm