P2624 [HNOI2008] Mingming's Worries

Original: "Compilation Optimization". See P1792.

Ever since Mingming learned about tree structures, he has become interested in unusual trees. Given nodes labeled $1$ to $N$, and the final degrees of some nodes, you may add edges between any pair of nodes. How many trees can be formed whose degrees meet the given requirements?

The first line contains a positive integer $N$ ($0 < N \le 1000$). The next $N$ lines: the $(i+1)$-th line contains a positive integer representing the degree $D_i$ of the $i$-th node. If the degree is unconstrained, input `-1`.

Output a single positive integer on one line, the number of different trees that satisfy the requirements. If there is no solution, output $0$.

The two trees are `1-2-3` and `1-3-2`. Translated by ChatGPT 5