C++14(g++5.4) 解法, 执行用时: 30ms, 内存消耗: 26504K, 提交时间: 2020-08-23 13:53:32

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
int n,k;
vector<int> v[2010];
ll dp[2010][2010];
int si[2010];
ll p[2010];
void dfs(int x,int fa)
{
	si[x]=1;
	dp[x][1]=1;
	for(int i:v[x])
	{
		if(i==fa)
		continue;
		dfs(i,x);
		memset(p,0,sizeof p);
		for(int j=1;j<=si[x];j++)
		{
			for(int f=0;f<=min(k-j,si[i]);f++)
			{
				p[f+j]=(p[f+j]+dp[x][j]*dp[i][f]%mod)%mod;
			}
		}
		for(int j=1;j<=k;j++)
		dp[x][j]=p[j];
		si[x]+=si[i];
	}
	for(int i=1;i<=k;i++)
	dp[x][0]+=dp[x][i];
	dp[x][0]%=mod;
 } 
 int main()
 {
 	scanf("%d%d",&n,&k);
 	for(int i=1,x,y;i<n;i++)
 	{
 		scanf("%d%d",&x,&y);
 		v[x].push_back(y);
 		v[y].push_back(x);
	 }
	 dfs(1,0);
	 printf("%lld",dp[1][0]);
 }

C++11(clang++ 3.9) 解法, 执行用时: 41ms, 内存消耗: 30104K, 提交时间: 2020-08-04 18:47:41

#include<bits/stdc++.h>
using namespace std;

const int mod=998244353;
int i,j,n,t,DP[2005][2005],size[2005];
vector<int>R[2005];
void DFS(int x,int fa)
{
	int i,j,k,l,S[2005];
	size[x]=DP[x][1]=1;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(j==fa)continue;
		DFS(j,x),memset(S,0,sizeof(S));
		for(k=0;k<=size[x];k++)
			for(l=0;l<=size[j];l++)S[k+l]=(S[k+l]+(long long)DP[x][k]*DP[j][l])%mod;
		for(k=0;k<=size[x]+size[j];k++)DP[x][k]=S[k];
		size[x]+=size[j];
	}
	for(i=1;i<=t;i++)DP[x][0]=(DP[x][0]+DP[x][i])%mod;
}
int main()
{
    scanf("%d%d",&n,&t),n--;
    while(n--)
    {
    	scanf("%d%d",&i,&j);
		R[i].push_back(j),R[j].push_back(i);
	}
    DFS(1,0);
    printf("%d\n",DP[1][0]);
    return 0;
}