题意：给你一棵树，问你切掉某些边使得得到的所有子树的直径都小于等于\(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;
}
F. Diameter Cuts from Educational Codeforces Round 106 (Rated for Div. 2)
原文：https://www.cnblogs.com/ruanbaiQAQ/p/14635740.html