F. Diameter Cuts from Educational Codeforces Round 106 (Rated for Div. 2)

题意：给你一棵树，问你切掉某些边使得得到的所有子树的直径都小于等于(k)的方案数。（树的直径：树中最长的简单路径）

记(dp[i][j])，表示以i为根的直径为j子树的答案方案数。对于每个节点(i)，一开始(dp[i][0]=1)（以(i)为根的直径为0的子树的方案数），之后对于与(i)相连的每棵子树的根节点(y)，有(2)种合并情况：

①i与y相连的这条边断开，即(i)可以分出的最大直径为(a)，(y)可以分出的最大直径为(b)，那么 (dp[y][])的所有方案都可以与(dp[i][])累乘
即： (sum_{j=0}^a dp_{ij}*sum_{j=0}^b dp_{yj})

②(i)与(y)相连的这条边不断开，则(i)的最大直径就需要去更新（要与(k)取min），同时枚举(i)的直径(a)和(y)的直径(b)（(a+b+1<=k))，加入对应直径的dp数组即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
ll mod = 998244353;

int n, k, mx[5050];
vector<int>G[5050];
ll dp[5005][5005], tmp[5005];

void dfs(int from, int fa)
{
	dp[from][0] = 1;
	for (auto to : G[from])
	{
		if (to == fa)continue;
		dfs(to, from);
		for (int i = 0; i <= max(mx[from], mx[to] + 1); i++)tmp[i] = 0;
		ll sum = 0;
		for (int i = 0; i <= mx[to]; i++)
			sum = (sum + dp[to][i]) % mod;
		for (int i = 0; i <= mx[from]; i++)
			tmp[i] = (dp[from][i] * sum) % mod;
		for (int i = 0; i <= mx[from]; i++)
			for (int j = 0; i + j + 1 <= k && j <= mx[to]; j++)
				tmp[max(i, j + 1)] = (tmp[max(i, j + 1)] + dp[from][i] * dp[to][j]) % mod;
		mx[from] = min(max(mx[from], mx[to] + 1), k);
		for (int i = 0; i <= mx[from]; i++)
			dp[from][i] = tmp[i];
	}
}

int main()
{
	fastio;
	cin >> n >> k;
	for (int i = 1; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1, -1);
	ll ans = 0;
	for (int i = 0; i <= mx[1]; i++)
		ans = (ans + dp[1][i])% mod;
	cout << ans;
	return 0;

}