← 返回题目列表

Codeforces · 1499/F

F. 直径切割

中文机器翻译题面 查看原题

给定一个整数 $$$k$$$ 和一棵由 $$$n$$$ 个顶点组成的无向树。

某对顶点之间的简单路径(每个顶点最多出现一次的路径)的长度是该路径中的边数。树的直径是该树的所有顶点对之间的简单路径的最大长度。

您即将从树中删除一组边。当边缘被移除时,树会分裂成多个较小的树。如果所有生成的树的直径小于或等于 $$$k$$$,则该边集有效。

如果有一条边仅出现在其中一组边中,则两组边是不同的。

计算有效边集的数量,以 $$$998\,244\,353$$$ 为模。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 5000$$$, $$$0 \le k \le n - 1$$$) - 分别是树的顶点数和最大允许直径。

接下来的 $$$n-1$$$ 行中的每一行都包含一条边的描述:两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \neq u$$$)。

给定的边形成一棵树。

输出

打印单个整数 - 有效边集的数量以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

4 3
1 2
1 3
1 4

输出 #1

8

输入 #2

2 0
1 2

输出 #2

1

输入 #3

6 2
1 6
2 4
2 6
3 6
5 6

输出 #3

25

输入#4

6 3
1 2
1 5
2 3
3 4
5 6

输出#4

29

注意

在第一个示例中,给定树的直径已经小于或等于 $$$k$$$。因此,您可以选择任何一组要删除的边,生成的树的直径将小于或等于 $$$k$$$。有 $$$2^3$$$ 套,包括空的一套。

在第二个示例中,您必须删除唯一的边。否则,直径将为 $$$1$$$,大于 $$$0$$$。

这是第三个和第四个示例的树: