朴素的设计 \(DP\)，\(dp_{i,j,0/1,0/1}\) 表示 \(i\) 的子树选了 \(j\) 个点，当前选没有，当前被覆盖没有。
令人火大的转移方程（具体转移边界还请看代码）：
\[\begin{align}&dp_{u,j,0,0} = \sum_{k=1}^{siz_u} dp_{u,k,0,0} \times dp_{v,j-k,0,1}
\\
&dp_{u,j,0,1} =
\begin{cases}
\sum_{k=1}^{siz_u} dp_{u,k,0,0} \times dp_{v,j-k,1,1}
\\
\sum_{k=1}^{siz_u} dp_{u,k,0,1} \times dp_{v,j-k,0,1}
\\
\sum_{k=1}^{siz_u} dp_{u,k,0,1} \times dp_{v,j-k,1,1}
\end{cases}
\\
&dp_{u,j,1,0} =
\begin{cases}
\sum_{k=1}^{siz_u} dp_{u,k,1,0} \times dp_{v,j-k,0,0}
\\
\sum_{k=1}^{siz_u} dp_{u,k,1,0} \times dp_{v,j-k,0,1}
\end{cases}
\\
&dp_{u,j,1,1} =
\begin{cases}
\sum_{k=1}^{siz_u} dp_{u,k,1,0} \times dp_{v,j-k,1,0}
\\
\sum_{k=1}^{siz_u} dp_{u,k,1,0} \times dp_{v,j-k,1,1}
\\
\sum_{k=1}^{siz_u} dp_{u,k,1,1} \times dp_{v,j-k,0,0}
\\
\sum_{k=1}^{siz_u} dp_{u,k,1,1} \times dp_{v,j-k,0,1}
\\
\sum_{k=1}^{siz_u} dp_{u,k,1,1} \times dp_{v,j-k,1,0}
\\
\sum_{k=1}^{siz_u} dp_{u,k,1,1} \times dp_{v,j-k,1,1}
\end{cases}\end{align}
\]
最后注意转移边界以及外层倒序枚举就行了。
\(\Large \mathscr{Code}\)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100, MOD = 1e9 + 7;
int n, m, dp[N][105][2][2], k, siz[N];
vector<int> g[N];
void dfs(int u, int fa) {siz[u] = dp[u][0][0][0] = dp[u][1][1][0] = 1;for (int e : g[u]) {if (e == fa) continue;dfs(e, u);siz[u] += siz[e];for (int i = min(k, siz[u]); i >= 0; i--) {int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;for (int j = 0; j <= min(i, siz[e]); j++) {if (i - j > siz[u] - siz[e]) continue;sum1 = (sum1 + 1ll * dp[u][i - j][0][0] * dp[e][j][0][1] % MOD) % MOD;sum2 = (sum2 + 1ll * dp[u][i - j][0][0] * dp[e][j][1][1] % MOD) % MOD;sum2 = (sum2 + 1ll * dp[u][i - j][0][1] * dp[e][j][0][1] % MOD) % MOD;sum2 = (sum2 + 1ll * dp[u][i - j][0][1] * dp[e][j][1][1] % MOD) % MOD;sum3 = (sum3 + 1ll * dp[u][i - j][1][0] * dp[e][j][0][0] % MOD) % MOD;sum3 = (sum3 + 1ll * dp[u][i - j][1][0] * dp[e][j][0][1] % MOD) % MOD;sum4 = (sum4 + 1ll * dp[u][i - j][1][0] * dp[e][j][1][0] % MOD) % MOD;sum4 = (sum4 + 1ll * dp[u][i - j][1][0] * dp[e][j][1][1] % MOD) % MOD;sum4 = (sum4 + 1ll * dp[u][i - j][1][1] * dp[e][j][0][0] % MOD) % MOD;sum4 = (sum4 + 1ll * dp[u][i - j][1][1] * dp[e][j][0][1] % MOD) % MOD;sum4 = (sum4 + 1ll * dp[u][i - j][1][1] * dp[e][j][1][0] % MOD) % MOD;sum4 = (sum4 + 1ll * dp[u][i - j][1][1] * dp[e][j][1][1] % MOD) % MOD;}dp[u][i][0][0] = sum1, dp[u][i][0][1] = sum2, dp[u][i][1][0] = sum3, dp[u][i][1][1] = sum4;}}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> k;for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;g[x].push_back(y), g[y].push_back(x);}dfs(1, 0);cout << (dp[1][k][0][1] + dp[1][k][1][1]) % MOD;return 0;
}