蓝魔法师 题解

用dp[j][k]表示j结点的连通块 大小为k的方案数
然后从叶子结点一路递推回来，分类讨论。
如果不切掉连着的边，两个连通块合并，方案数就是直接相乘
dp[u][j+k]= dp[u][j]*dp[to][k]
如果切掉连着的边，方案数就是独立的
那么就是加上孩子的dp和，dp[u][j]=dp[u][j] * dp[v][k]

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
ll n,k;
ll dp[2020][2020];//第一维度表示谁的连通块 第二维度表示连通块大小 值存方案数
ll _size[2020];
struct node
{
    int v,next;
}e[4040];
int cnt=0,head[2020];
void add(int u,int v)
{
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int pre)
{
    dp[u][1]=_size[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to==pre) continue;
        dfs(to,u);
        ll sum=0;
        for(int j=1;j<=min(_size[to],k);j++)
        {
            sum+=dp[to][j];
            sum%=mod;
        }
        for(int j=min(_size[u],k);j>=1;j--)
        {
            for(int p=min(_size[to],k);p>=1;p--)
            {
                if(j+p>k) continue;
                dp[u][j+p]=(dp[u][j+p]+dp[u][j]*dp[to][p])%mod;
            }
            dp[u][j]*=sum;
            dp[u][j]%=mod;
        }
        _size[u]+=_size[to];
    }
}
int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,1);
    ll ans=0;
    for(int i=1;i<=k;i++)
    {
        ans=(ans+dp[1][i])%mod;
    }
    printf("%lld\n",ans);
}