Submit solution
Points:
25 (partial)
Time limit:
0.6s
Memory limit:
162M
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Count the number of distinct spanning trees that exist on labeled vertices,
given that some of these vertices are restricted in their degree.
Constraints
In test data worth 30% of marks, you may assume .
Input Specification
The first line contains a single positive integer, .
Each of the next lines contains a single integer,
. If
is
-1
, then there is no degree restriction on vertex . Otherwise,
vertex
must have degree
.
Output Specification
Output the number of distinct spanning trees.
Sample Input
3
-1
-1
1
Sample Output
2
Comments
Just read the formula at the end of this link.