bzoj 1211: [HNOI2004]树的计数 — purfer序列

  • 2017-03-17
  • 0
  • 0

 

1211: [HNOI2004]树的计数

Time Limit: 10 Sec  Memory Limit: 162 MB

Description

一个有n个结点的树,设它的结点分别为v1, v2, …, vn,已知第i个结点vi的度数为di,问满足这样的条件的不同的树有多少棵。给定n,d1, d2, …, dn,编程需要输出满足d(vi)=di的树的个数。

Input

第一行是一个正整数n,表示树有n个结点。第二行有n个数,第i个数表示di,即树的第i个结点的度数。其中1<=n<=150,输入数据保证满足条件的树不超过10^17个。

Output

输出满足条件的树有多少棵。

Sample Input

4
2 1 2 1

Sample Output

2

HINT

每一棵树都对应着唯一的prufer数列,prufer数列也对应唯一的树。prufer数列构造方法:选取编号最小的叶子节点删掉,并将它的父亲加入到prufer数列中,直到树上还有两个节点。假设一个点入度为d,它最多有可能在prufer上出现(d-1)次(普通节点不可能因为父亲出现在prufer上,根节点由于prufer构造时要留两个点所以也会有一个儿子无法使它出现在prufer上)  ,所以一共有n-2个数字出现在prufer上,其中每个相同数字出现d-1次,所以答案为

(n – 2) ! / ( (d1 – 1)! (d2 – 1)! ……(dn – 1)! )

 

评论

还没有任何评论,你来说两句吧