[HNOI2004]树的计数(prufer编码)

2017年08月25日 14点热度 0人点赞 0条评论

1211: [HNOI2004]树的计数

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2609  Solved: 937
[Submit][Status][Discuss]

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

/*
prufer编码的推广,n个节点的度依次为D1, D2, …, Dn的无根树共有(n-2)! / [ (D1-1)!(D2-1)!..(Dn-1)! ]个(Di为结点i的度数,可能需要判断下度数之和是否等于结点数*2-2,度数为0的时候只能在n等于1时出现)
*/
#include
#include
#include
using namespace std;
map p1,p2;
int main() {
	int n,sum=0,ff=0;
	cin>>n;
	for(int i=0; i>tt;
		if(!tt) ff=1;
		sum+=tt;
		tt--;
		for(int t=2; t<=tt; ++t) {
			for(int i=2; i*i<=t; ++i)
				while(t%i==0) p1[i]++,t/=i;
			if(t!=1) p1[t]++;
		}
	}
	if(ff==1&&n>1||sum!=n*2-2) {
		cout<<0<
未经允许不得转载![HNOI2004]树的计数(prufer编码)

update

纸上得来终觉浅, 绝知此事须躬行。