一棵树的Prufer数列
每次在剩下的树中找到标号最小的叶子节点（对于无根树而言即是度数为1的节点），删去。
同时将其父节点（即与其相连的唯一点）加入Prufer数列当中。
一个Prufer数列所对应的树
G集合开始为空集
设当前处理到Prufer数列的第i项，找到G集合中未出现且在Prufer[i..n-2]未出现过的标号最小的节点，设其为u。
将u加入集合G中，并将u与Prufer[i]连一条边。
最后将在G集合中仍未出现的两个点之间连一条边（其中必定有一个是n）。
来思考一下为何可以还原成最初的树
首先我们可以把加入G集合这个操作当成是删去叶子节点的操作。
在G集合中未出现代表这个数还在树上未被删去。
再Prufer[i..n-2]中未出现代表这个节点当前的度数为1，即是叶子节点。
所以找出的u其实就等同于标号最小的叶子节点。
显然，树和Prufer数列一一对应。
即对于一棵树有且仅有一个Prufer数列
对于一个Prufer数列能且仅能还原出唯一的一棵树。
一些性质
每一个Prufer数列有n-2项（n为节点的个数）
对于一个度数为x的节点，它在Prufer数列中出现x-1次
对于满足上述两个条件的Prufer数列（当然每个数不能超过n）必能构成一棵合法的树
有了这个想法便可以开始做这道题。
即求可能的Prufer数列的个数。
转化为一个排列组合问题
对于cnt个有度数限制的节点，其a[i]-1的加和我们设为sum，则要在Prufer数列的n-2个空位中选sum的位置放这cnt个点
对于剩下的n-sum-2个空位可以放任意的没有度数限制的点。
(n-2)!*(n-cnt)/(∏(a[i]-1)!*(n-sum-2)!)
求解上述式子可以用分解质因子的方法，对于阶乘的分解可以采用更快的方法。
最后高精度乘法。
program bzoj1005;
const maxn=;tt=;
type arr=array[-..maxn]of longint;
var n,cnt,sum,i,j:longint;
a,p,w:array[-..maxn]of longint;
vis:array[-..maxn]of boolean;
ans:arr;
ss:string;
procedure printf;
begin
writeln();
halt;
end; procedure build;
var i,j:longint;
begin
fillchar(vis,sizeof(vis),true);
p[]:=;
for i:= to maxn do
begin
if vis[i] then
begin
inc(p[]);
p[p[]]:=i;
end;
for j:= to p[] do
begin
if i*p[j]>maxn then break;
vis[i*p[j]]:=false;
if i mod p[j]= then break;
end;
end;
end; procedure work(x,y:longint);
var i,xx,tot:longint;
begin
xx:=x;
for i:= to p[] do
begin
x:=xx;tot:=;
while x<> do
begin
inc(tot,x div p[i]);
x:=x div p[i];
end;
inc(w[i],tot*y);
end;
end; procedure work2(x,y:longint);
var i,tot:longint;
begin
for i:= to p[] do if x mod p[i]= then
begin
tot:=;
while x mod p[i]= do
begin
inc(tot);x:=x div p[i];
end;
inc(w[i],tot*y);
end;
end; function mul(a:arr;b:longint):arr;
var c:arr;
i:longint;
begin
fillchar(c,sizeof(c),);
c[]:=a[];
for i:= to c[] do
begin
inc(c[i],a[i]*b);
inc(c[i+],c[i] div tt);
c[i]:=c[i] mod tt;
end;
if c[c[]+]<> then inc(c[]);
exit(c);
end; begin
//assign(input,'bzoj1005.in');reset(input);
//assign(output,'bzoj1005.out');rewrite(output);
readln(n);
cnt:=;sum:=;
for i:= to n do
begin
readln(a[i]);
if a[i]> then inc(cnt) else
if a[i]= then printf;
if a[i]> then inc(sum,a[i]-);
end;
fillchar(w,sizeof(w),);
if sum>n- then printf;
build;
work(n-,);
work(n--sum,-);
work2(n-cnt,n-sum-);
for i:= to n do if a[i]> then work(a[i]-,-);
ans[]:=;ans[]:=;
for i:= to p[] do
for j:= to w[i] do ans:=mul(ans,p[i]);
write(ans[ans[]]);
for i:=ans[]- downto do
begin
str(ans[i],ss);
for j:=length(ss)+ to do write();
write(ans[i]);
end;
end.