https://ac.nowcoder.com/acm/problem/20811
参考：https://blog.nowcoder.net/n/a52f02e1f87844e494690964fc6959dc
题意：
给出一棵树，求有多少种删边方案给出一棵树，求有多少种删边方案
使得删后的图每个连通块大小小于等于k使得删后的图每个连通块大小小于等于k
答案对998244353取模答案对998244353取模

题解：
n,k<=2000n,k<=2000
数据范围很明显能开一个二维dp数据范围很明显能开一个二维dp
需要的维护是连通块大小和点数需要的维护是连通块大小和点数
dp[i][j]表示i点连通块大小为j的方案数dp[i][j]表示i点连通块大小为j的方案数

然后考虑转移方程然后考虑转移方程
对于每棵子树，有两种可能对于每棵子树，有两种可能
1.不删除这条边，两个点相连
那么这个点的连通块大小就是两个点的连通块大小相加那么这个点的连通块大小就是两个点的连通块大小相加
对于方案数直接相乘对于方案数直接相乘
即dp[u][i+j]+=dp[u][i]*dp[v][j]

2.删除这条边，两个点各自独立2.删除这条边，两个点各自独立
dp[u][i]=dp[u][i]∗∑dp[v][j]

最后总方案数计算出dp[1]里的所有可行解最后总方案数计算出dp[1]里的所有可行解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>p;
const int N=2e3+5;
const int mod=998244353;
ll dp[N][N];
int n,k,T,sz[N];
vector<int>G[N];
void dfs(int u,int fa) {
    dp[u][1]=sz[u]=1;
    for(auto v:G[u]) {
        if(v==fa)continue;
        dfs(v,u);
        ll sum=0;///删掉的方案数
        for(int i=1; i<=min(k,sz[v]); i++) {
            sum=(sum+dp[v][i])%mod;
        }
        for(int i=min(k,sz[u]); i>=1; i--) {
            for(int j=min(k,sz[v]); j>=1; j--) {
                if(i+j<=k)
                    dp[u][i+j]=(dp[u][i+j]+dp[u][i]*dp[v][j])%mod;
            }
            dp[u][i]=dp[u][i]*sum%mod;
        }
        sz[u]+=sz[v];
    }
}
int main() {
    cin>>n>>k;
    for(int i=1,u,v; i<n; i++) {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    ll ans=0;
    for(int i=1; i<=k; i++)
        ans=(ans+dp[1][i])%mod;
    cout<<ans<<endl;
}