C++14(g++5.4) 解法, 执行用时: 542ms, 内存消耗: 138656K, 提交时间: 2020-02-01 23:55:37

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

#define fi first
#define se second
#define lch (o << 1)
#define rch (o << 1 | 1)

typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
typedef __int128 u128;

const int MOD = 998244353;
const int N = 1e4 + 5;
const int K = 500 + 5;

// f with pa, g without pa
ll f1[N][K], f2[N][K], g1[N][K], g2[N][K];
int siz[N];
vector<int> a[N];
int n, lim;

void DFS(int u, int pa){
	siz[u] = 1;
	f1[u][0] = g1[u][0] = 1;
	for(auto v: a[u]){
		if(v == pa) continue;
		DFS(v, u);
		siz[u] += siz[v];

		for(int i=min(lim, siz[u]); i>=0; i--){
			for(int j=0; j<=min(i, siz[v]); j++){
				if(i - j > siz[u] - siz[v]) continue;
				ll tmp = 0;
				if(j > 0) tmp += g2[v][j];
				if(j > 1) tmp += g1[v][j-1];
				
				f1[u][i] += f1[u][i-j] * tmp % MOD;
				f2[u][i] += f2[u][i-j] * tmp % MOD;
				g1[u][i] += g1[u][i-j] * tmp % MOD;
				g2[u][i] += g2[u][i-j] * tmp % MOD;

				f2[u][i] += f1[u][i-j] * (f1[v][j] + f2[v][j]) % MOD;
				g2[u][i] += g1[u][i-j] * (f1[v][j-1] + f2[v][j-1]) % MOD;
			}
			f1[u][i] %= MOD; f2[u][i] %= MOD;
			g1[u][i] %= MOD; g2[u][i] %= MOD;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);

	cin >> n >> lim;
	for(int i=1; i<n; i++){
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}

	DFS(1, 0);

	ll ans = 0;
	for(int i=0; i<=lim; i++){
		if(i < lim) ans = (ans + g1[1][i]) % MOD;
		ans = (ans + g2[1][i]) % MOD;
	}
	cout << (ans + MOD) % MOD << endl;

	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 81ms, 内存消耗: 40184K, 提交时间: 2020-03-06 18:55:23

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+5;
const int K = 5e2+5;
const ll mod = 998244353;

int n,k;
int sz[N];
ll f[N][K];
vector<int> G[N];

void dfs(int x,int fa=-1){
	sz[x]=1;
	for(int i=0;i<G[x].size();++i)
	if(G[x][i]!=fa){
		dfs(G[x][i],x);
	}
	static ll g[K][2],h[K][2];
	memset(g,0,sizeof(g));
	memset(h,0,sizeof(h));
	h[0][0]=1;
	for(int i=0;i<G[x].size();++i)
	if(G[x][i]!=fa){
		int y=G[x][i];
		for(int j=0;j<=min(k,sz[x]);++j){
			g[j][0]=h[j][0];
			g[j][1]=h[j][1];
			h[j][0]=h[j][1]=0;
		}
		for(int j=0;j<=min(k,sz[x]);++j)
		for(int t=0;t<=min(k-j,sz[y]);++t){
			(h[j+t][0]+=g[j][0]*f[y][t]%mod)%=mod;
			(h[j+t][1]+=g[j][1]*f[y][t]%mod)%=mod;
			if(t)(h[j+t][1]+=g[j][0]*f[y][t]%mod)%=mod;
			else (h[j+t+1][1]+=g[j][0]*f[y][t]%mod)%=mod;
		}
		sz[x]+=sz[y];
	}
	for(int i=1;i<=min(sz[x],k);++i){
		f[x][i]=h[i][1];
		if(i>1){
			(f[x][i]+=h[i-1][0])%=mod; 
		}
	}
	f[x][0]=1;
}

int main(){
	cin>>n>>k;
	for(int i=1,x,y;i<n;++i){
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1);
	int ans=0;
	for(int i=0;i<=k;++i)(ans+=f[1][i])%=mod;
	cout<<ans<<endl;
}