#P2290. [HNOI2004] 树的计数

    ID: 1302 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>排列组合数论数学组合数学各省省选2004湖南

[HNOI2004] 树的计数

题目描述

一个有 nn 个节点的树,设它的节点分别为 v1,v2,,vnv_1,v_2,\ldots,v_n,已知第 ii 个节点 viv_i 的度数为 did_i,问满足这样的条件的不同的树有多少棵。

输入格式

输入文件第一行是一个正整数 nn ,表示树有 nn 个结点。第二行有 nn 个数,第 ii 个数表示 did_i,即树的第 ii 个结点的度数。

输出格式

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

4                     
2 1 2 1
2

提示

1n1501\le n\le 150,保证满足条件的树不超过 101710^{17} 个。