前言

感受

思路














复杂度证明


图片说明



图片说明

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e3 + 10;
const ll mod = 998244353;
struct edge{
    int v, nex;
}e[maxn << 1];
int head[maxn], cnt;
int n, k, num[maxn];
ll sum[maxn];///sum[u] 表示以u为根的子树中,删除后所有连通块个数均小于等于k的总数
ll dp[maxn][maxn];///dp[u][x] 表示以u为根的子树中,删除后所有连通块个数均小于等于k,且u所在的连通块大小为x
void add_edge(int u, int v){
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    for(int i = 1; i <= n; i++){
        head[i] = -1;
    }
}
void dfs(int u, int fa){
    int v; dp[u][1] = 1; num[u] = 1;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa) continue;
        dfs(v, u);
        /**断边*/
        ///对于每一项dp[u][x] *= sum[v];
        /**不断边*/
        for(int x = min(num[u], k); x >= 1; x--){
            for(int j = 1; j <= min(num[v], k); j++){
                if(x + j > k) continue;
                dp[u][x + j] = dp[u][x + j] + dp[v][j] * dp[u][x] % mod;
                dp[u][x + j] %= mod;
            }
            dp[u][x] = dp[u][x] * sum[v] % mod;
        }
        num[u] += num[v];
    }
    for(int x = min(num[u], k); x >= 1; x--){
        sum[u] = sum[u] + dp[u][x]; sum[u] %= mod;
    }
}
int main(){
    scanf("%d%d", &n, &k);
    init();
    int u, v;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }
    dfs(1, 0);
    printf("%lld\n", sum[1]);
    return 0;
}