好题啊！
题意很明白，对于有关最小生成树(MST)的题，一般是要模拟 Kruskal 过程了；
模拟 Kruskal，也就是把给出的 n-1 条边一条一条加进去，那么就要枚举每次连接了哪两个连通块(点集)；
于是需要记录连通块情况，这样加一条边就相当于一种情况到另一种情况的转移，就可以DP；
记录连通块情况较为复杂，而且还要注意不重复等等...
但实际上，我们在转移时，并不需要知道连通块中有哪些点，只要知道连通块的大小即可(从n个1开始转移时已有所区分)；
所以可以通过 dfs 求出所有连通块情况(枚举连通块个数及大小)，把它们哈希记录下来；
然后就可以转移，从 i+1 个点集转移到 i 个点集，需要枚举是哪两个点集合并了；
答案的增加体现在合并点集时连的 MST 边有点数×点数种方案，而且一个点集状态中不是 MST 边的边可以分配权值；
代码挺复杂而精美...模仿了一篇AC代码，为了看懂加了许多注释，都挪过来了。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int const maxn=,maxm=,mod=1e9+,base=;//
int n,s,a[maxn],vec[maxn][maxm][maxn],len[maxn],edg[maxn][maxm],tmp[maxn];
int inv[maxn*maxn],jc[maxn*maxn],jcn[maxn*maxn],f[maxn][maxm],id[maxn][maxn];
map<ull,int>mp[maxn];
void init()
{
inv[]=jc[]=jcn[]=;
for(int i=;i<maxn*maxn;i++)inv[i]=((ll)(mod-mod/i)*inv[mod%i])%mod;//
for(int i=;i<maxn*maxn;i++)jc[i]=((ll)jc[i-]*i)%mod,jcn[i]=((ll)jcn[i-]*inv[i])%mod;//
}
void dfs(int nw,int i,int lst)//剩余点数,已有点集数,上一个点集的点数
{
if((s-i+)*lst>nw)return;//剩余点集数*上一个点集点数(剩余点数总和的极小值)>剩余点数总和
if(i==s+)
{
len[s]++; ull hsh=;//hsh 不是 int,不能 mod!
for(int j=;j<=s;j++)
{
vec[s][len[s]][j]=tmp[j];//s个点集的情况中第len[s]种状态的各个点集
edg[s][len[s]]+=((tmp[j]*(tmp[j]-))>>);//C(tmp[j],2)
hsh=hsh*base+tmp[j];
}
mp[s][hsh]=len[s]; return;//s中的这种状态的哈希值对应编号
}
else if(i==s)tmp[i]=nw,dfs(,i+,nw);
else for(int j=lst;j<=nw;j++)tmp[i]=j,dfs(nw-j,i+,j);//=
}
ll P(int n,int m)// n!/(n-m)!
{
if(n<m)return ;
return (ll)jc[n]*jcn[n-m]%mod;
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)scanf("%d",&a[i]); reverse(a+,a+n);//从大到小
init();
for(s=;s<=n;s++)dfs(n,,);//选点集方案,点数总和为n
f[n][]=;//
for(int i=n;i>;i--)//i个点集 //i>1
for(int j=;j<=len[i];j++)
{
f[i][j]=((ll)f[i][j]*P(edg[i][j]-a[i],a[i-]-a[i]-))%mod;//分配权值 //a[i-1]>a[i]
//(各点集内部的)总边数-a[i] 中选 a[i-1]~a[i] 权值的边的方案(前n-i小的边用于点集内部形成MST的前n-i条边,剩余i个点集)
//有a[i]条边在之前被连,否则轮不到这条MST边来改变连通性
//若该状态不存在,则P(n,m)中n<m,值为0 //n>m 多余空位可在最后补
memset(id,,sizeof id);
for(int k=;k<=i;k++)tmp[k]=vec[i][j][k];
for(int k=;k<=i;k++)
for(int l=k+;l<=i;l++)
{
if(!id[tmp[k]][tmp[l]])//(记忆化) //k,l各不相同但tmp[k],tmp[l]可能相同
{
ull hsh=; bool flag=;
for(int p=;p<=i;p++)//tmp[k,l,p]都以点数代表点集
{
if(p==k||p==l)continue;
if(!flag&&tmp[p]>tmp[k]+tmp[l])flag=,hsh=hsh*base+tmp[k]+tmp[l];
//第一个p>k+l(点数,保证从小到大哈希),把k,l作为一个连通块哈希
hsh=hsh*base+tmp[p];
}
if(!flag)hsh=hsh*base+tmp[k]+tmp[l];//!
id[tmp[k]][tmp[l]]=mp[i-][hsh];
}
int d=id[tmp[k]][tmp[l]];//此哈希值对应的选点集状态编号(k,l作为一个连通块)
f[i-][d]=(f[i-][d]+(ll)f[i][j]*tmp[k]*tmp[l])%mod;//连接点集的边是MST边,有点数*点数种连边方案
}
}
// f[1][1]=((ll)f[1][1]*jc[a[1]-1])%mod;
f[][]=((ll)f[][]*jc[edg[][]-a[]])%mod;//剩余空位
printf("%d\n",f[][]);
return ;
}