题目：蓝魔法师
分析：
dp[i][j]表示对于i这个子树来说，i所在的连通块大小为j，并且整棵树合法的方案数。 接下来就是类似背包的解法了。遍历每个儿子的分支，每个分支要么删除，要么不删除。 1.删除：
删除此边，那么就意味着当前以u节点连通块大小为k的方案数 都可以 乘 v节点连通块大小所有的方案数：
2.不删除
不删除就相当于合并那么此时直接跑两个循环即可：
for(int i=1;i<=min(sz[u]*1ll,m);i++){
for(int k=1;k<=min(sz[e]*1ll,m);k++){
if(i+k<=m){
tmp[i+k] += (dp[u][i]*dp[e][k])%mod;
tmp[i+k] %=mod;
}
}
}
考虑到和dp[u][k]的状态有关，所以用tmp数组先预初储存一下！
代码：
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define x first
#define y second
typedef pair
<int, int> par
;
const ll mod
= 998244353;
const int maxn
= 2e3 + 10;
const int inf
= 0x3f3f3f3f;
ll n
, k
;
vector
<int> g
[maxn
];
ll dp
[maxn
][maxn
], tmp
[maxn
];
ll siz
[maxn
];
void dfs(int u
, int fa
)
{
siz
[u
] = 1, dp
[u
][1] = 1;
for(int v
: g
[u
])
{
if(v
== fa
) continue;
dfs(v
, u
);
ll sum
= 0;
for(int i
= 1; i
<= min(siz
[v
], k
); i
++)
sum
+= dp
[v
][i
], sum
%= mod
;
for(int i
= 1; i
<= min(siz
[u
], k
); i
++)
for(int j
= 1; j
<= min(siz
[v
], k
); j
++)
if(i
+ j
<= k
)
tmp
[i
+ j
] += dp
[u
][i
] * dp
[v
][j
] % mod
, tmp
[i
+ j
] %= mod
;
siz
[u
] += siz
[v
];
for(int i
= 1; i
<= min(siz
[u
], k
); i
++)
dp
[u
][i
] = (sum
* dp
[u
][i
] % mod
+ tmp
[i
]) % mod
;
mem(tmp
, 0);
}
}
int main()
{
cin
>> n
>> k
;
for(int i
= 1; i
< n
; i
++)
{
int a
, b
; cin
>> a
>> b
;
g
[a
].pb(b
), g
[b
].pb(a
);
}
dfs(1, -1);
ll res
= 0;
for(int i
= 1; i
<= k
; i
++)
res
= (res
+ dp
[1][i
]) % mod
;
cout
<< res
<< endl
;
}
