称编号 \(> n\) 的点为新点。
由条件 1 可以推出树 \(T\) 为结点 \(1 \sim n\) 在树 \(T'\) 上的 虚树。
由条件 2 可以推出 \(\forall 1 \le u < v \le n + m, \operatorname{lca}(u, v) \le v + k\)。
首先考虑 \(k = 0\) 的做法：
此时 \(\forall 1 \le u < v \le n + m, \operatorname{lca}(u, v) \le v\)。
考虑从小到大加入新点 \(i\)，则需要满足 \(\max\limits_{j = 1}^i \{\operatorname{lca}(i, j)\} \le i\)，即 \(i\) 只能插在一条边上或挂为叶子结点，故答案为：
把从小到大加入新点的做法延续到 \(k > 0\) 的情况考虑：
此时 \(\forall 1 \le u < v \le n + m, \operatorname{lca}(u, v) \le v + k\)，和上面唯一的区别就是会存在 \(i \in [1, n], j \in [n + 1, n + m]\)，满足 \(\operatorname{lca}(i, j) \in [j + 1, j + k]\)。
考虑此时出现了哪些加点的新方式，归纳后可以发现在插入 \(i\) 时，可以把 \(j ( i + 1 \le j \le i + k)\) 插在树的某条边上，再将 \(i\) 挂为 \(j\) 的儿子。
总之，加点时有如下三种选择（令每次操作前树的大小为 \(sz\)）：
- 将 \(i\) 插在一条边上或挂为叶子结点，方案数 \(2sz - 1\)。
- 在某条边上新建一个待定结点并将 \(i\) 挂在其下，方案数 \(sz - 1\)。
- 用 \(i\) 填上某个待定结点。
\(k \le 10\)，又是树上的计数问题，状压 DP 就好。
令 \(f(i, S)\) 表示插入了 \(i\) 个点，前 \(k\) 个加点操作的剩余待定结点状态为 \(S\) 时的方案数，按三种情况转移就好，注意 \(sz = i + \operatorname{popcount(S)}\)。
时间复杂度 \(\mathcal O(t \cdot 2^kkm)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
constexpr int MAXN = 3e4 + 10, MAXM = 3e3 + 10, MOD = 1e9 + 7;
int n, m, k, fa[MAXN];
ull f[MAXM][1 << 10];
void solve() {
cin >> n >> m >> k;
for (int i = 2; i <= n; i++) cin >> fa[i];
if (k == 0) {
ull ans = 1;
for (int i = n; i < n + m; i++) (ans *= ((i << 1) - 1)) %= MOD;
cout << ans << '\n';
return;
}
memset(f, 0, sizeof(f)), f[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int S = 0; S < (1 << k); S++) {
if (!f[i][S]) continue;
for (int j = S; j; j -= j & (-j)) {
int toS = (S ^ (j & (-j))) << 1;
if (toS < (1 << k)) (f[i + 1][toS] += f[i][S]) %= MOD;
}
if ((S << 1) < (1 << k)) {
int sz = n + i + __builtin_popcount(S);
(f[i + 1][S << 1] += f[i][S] * ((sz << 1) - 1)) %= MOD;
(f[i + 1][S << 1 | 1] += f[i][S] * (sz - 1)) %= MOD;
}
}
}
cout << f[m][0] << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
int c, t; cin >> c >> t;
while (t--) solve();
return 0;
}