思路

思路应该算是比较简单吧...
难点在于时间复杂度的证明.
因为这题和的范围都是以内的.题目是让你切成若干份,每份大小都不超过,因为是一棵树,所以很容易想到树形.对于树形,我们很容易想到利用子树就行转移.那么我们要转移什么,才能让子树来跟新父节点呢?很显然的一个东西,我可以和子树分割,也可以不和子树分割.我们定义的状态表示到了这个节点所连的联通块大小为的方案数.
那么显然的转移方程就是:

假如不切割这颗子树,.
假如切割这颗子树,那么就相当于一个独立事件,对于的每种连通块大小都有可能,然后相乘即使答案了.

下面就是时间复杂度证明,简单一看好像是的.不过其实跑不满~~.时间真的卡的很紧,但绝对不是的.
倒叙枚举,防止更新的答案作为结果更新后面的答案.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=2e3+5;
ll n,k;
vector<int>g[N];
ll f[N][N],sz[N];
void dfs(int u,int fa)
{
    sz[u]=1;f[u][1]=1;
    for(int v:g[u])
    {
        if(v==fa)   continue;
        dfs(v,u);
        ll sum=0;
        for(int i=1;i<=min(sz[v],k);i++)    sum+=f[v][i],sum%=mod;
        for(int i=min(sz[u],k);i>=1;i--)//枚举父亲节点的连通块的大小.
        {
            for(int j=min(sz[v],k);j>=1;j--)//枚举子节点的连通块大小.
                if(i+j<=k) f[u][i+j]+=f[u][i]*f[v][j],f[u][i+j]%=mod;
            f[u][i]*=sum,f[u][i]%=mod;
        }
        sz[u]+=sz[v];
    }
}

int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,1);
    ll ans=0;
    for(int i=1;i<=k;i++)   ans+=f[1][i],ans%=mod;
    printf("%lld\n",ans);
    return 0;
}