蓝魔法师_牛客博客

题解：
树形dp
对于每棵子树，有两种可能
1.不删除这条边，两个点相连 $dp[u][i+j]+=dp[u][i]∗dp[v][j]$
2.删除这条边，两个点各自独立 $dp[u][i]=dp[u][i]∗∑dp[v][j]dp[u][i]=dp[u][i]*\sum{dp[v][j]}dp[u][i]=dp[u][i]∗∑dp[v][j]$

定义dp[i][j] 表示 i 结点所在的连通块中节点数为 j 的方案数是多少

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include<string.h>
#include <list>
#include <set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <cctype>
#include<iomanip>
#define int long long
#define endl '\n'
using namespace std;
const int maxn = 2010;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const ll mod= 998244353;
using namespace std;
int n, kk;
vector<int> v[maxn];
ll dp[maxn][maxn];
ll isize[maxn], num[maxn];


inline void add(int x,int y){
    v[x].push_back(y);
    v[y].push_back(x);
}

void dfs(ll x, ll fa){
    dp[x][1]=1;
    isize[x]=1;
    for(ll i = 0; i < v[x].size(); i++){
        ll to = v[x][i];
        if (to == fa) continue;
        dfs(to, x);

        for(ll j=1; j <= isize[x]; j++){
            for(ll k = 0; k <= isize[to]; k++){
                if (j+k > kk) break;
                num[j+k] += dp[x][j]*dp[to][k];
                num[j+k] %= mod;
            }
        }
        isize[x] += isize[to];
        for(ll j = 1; j <= isize[x]; j++) dp[x][j] = num[j], num[j] = 0;
    }
    for(ll i = 1; i <= kk; i++){
        dp[x][0] = (dp[x][0]+dp[x][i])%mod;
    }
}

signed main() {
    cin >> n >> kk;
    ll x, y;

    for(ll i = 1; i < n; i++){
        cin>>x>>y;
        add(x,y);
    }
    dfs(1, 0);
    ll ans = 0;
    for(ll i = 1; i <= kk; i++) ans = (ans+dp[1][i])%mod;
    cout<<ans<<endl;
    return 0;
}