\(k=0\)
考试时脑抽，现在想一想感觉挺简单的。
从小到大依次加点，那么题目的条件等价于每次可以把点加在一条边中间，或者加入一个叶子，并且这两种方式都会导致下一个点加入时可选的方案加二。
把方案数乘起来就好了。
\(k>0\)
需要一点观察。
除了上述两种加点的方式，还存在一种方式是，选择一个节点 \(x<y\le x+k\)，把 \(y\) 加在一条边中，\(x\) 作为 \(y\) 的儿子。
容易证明这样可以不重不漏地搜索所有的合法树。
那么状压记录一下 \([x+1,x+k]\) 这段区间有多少点已经被加入树里面，转移分三种讨论就行了。
复杂度 \(O(m2^kk)\)
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int dp[2][(1<<12)];
void solve()
{
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<n;i++)
{
int x;
scanf("%d",&x);
}
int U=(1<<k)-1;
for(int c=0;c<=1;c++)
for(int i=0;i<=U;i++)
dp[c][i]=0;
int cur=0;
dp[0][0]=1;
for(int p=1;p<=m;p++)
{
int nxt=(cur^1);
for(int i=0;i<=U;i++)if(dp[cur][i])
{
if(i&1)
{
dp[nxt][i>>1]=(dp[nxt][i>>1]+dp[cur][i])%mod;
dp[cur][i]=0;
continue;
}
int s=n+p-1;
for(int j=0;j<k;j++)if((i>>j)&1)s++;
dp[nxt][i>>1]=(dp[nxt][i>>1]+1ll*dp[cur][i]*(2*s-1)%mod)%mod;
for(int j=1;j<=k;j++)if((i>>j)%2==0)
dp[nxt][(i|(1<<j))>>1]=(dp[nxt][(i|(1<<j))>>1]+1ll*dp[cur][i]*(s-1)%mod)%mod;
dp[cur][i]=0;
}
cur=nxt;
}
printf("%d\n",dp[cur][0]);
}
int main()
{
int tp,T;
cin>>tp>>T;
while(T--)
{
solve();
}
return 0;
}