#PQJ2732x16026. QOJ 2732_16026
QOJ 2732_16026
自从明明学了树结构,他对奇形怪状的树产生了浓厚的兴趣。在画了一棵又一棵各种各样的树后,他想到了一个问题:给定 𝑛 个标号为 1 到 𝑛 的点,并允许在两点之间任意连线,要求最终连成一棵含 𝑛 个点的树,总共能画出多少棵不同的树呢?在着手解决这个问题的时候,他又想到另一个更一般的问题:给定 𝑛 个标号为 1 到 𝑛 的点以及某些点最终的度数,并允许在两点之间任意连线,要求最终连成一棵含 𝑛 个点的树且树中各点的度满足上述要求,总共能画出多少棵不同的树呢?
明明思考了很久,也只会手算一些简单的情况,由于初学程序设计,他不知道如何写个程序来帮他解决这个问题。所以求助于准备参加 NOI2008 的你,请你帮他解决这个问题。
输入格式
第一行包含一个整数 𝑛 ,表示树中的结点数,接下来的 𝑛 行依次表示结点 1 到结点 𝑛 最终应该具有的度数,第 𝑖 + 1 行表示结点 𝑖 最终应该具有的度数 𝐷 𝑖 ,若第 𝑖 行为 − 1 ,则表示对结点 𝑖 的度数没有要求。输入数据保证 0 < 𝑛 ≤ 1000 , − 1 ≤ 𝐷 𝑖 < 𝑛 。
输出格式
仅包含一个整数,表示可以画出多少棵不同的树,若无解则输出 0 。
样例数据 样例 1 输入 3 1 -1 -1 样例 1 输出 2