← 返回题目列表

Codeforces · 735/E

E. Ostap 和树

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

奥斯塔普已经在里约热内卢郊区定居下来,并开始在他的花园里种一棵树。回想一下,树是一个连通的无向无环图。

Ostap 的树现在有 n 个顶点。他想把树的一些顶点涂成黑色,这样从任何顶点 u 开始,至少有一个距离不超过 k 的黑色顶点 v。树的两个顶点之间的距离是它们之间路径的最小可能边数。

由于绘制树的方法数量可能很大,Ostap 希望您以 109 + 7 为模来计算它。如果存在以一种方式涂黑而未用另一种方式涂黑的顶点,则两种绘制树的方法被认为是不同的。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 100, 0 ≤ k ≤ min(20, n - 1)) - Ostap 树中的顶点数以及到最近黑色顶点的最大允许距离。不要错过 k 的异常约束。

接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n) - 由第 i 条边连接的顶点索引。保证给定的图是一棵树。

输出

打印一个整数 — 绘制树的方式数除以 1 000 000 007 (109 + 7) 所得的余数。

示例

输入 #1

2 0
1 2

输出 #1

1

输入 #2

2 1
1 2

输出 #2

3

输入 #3

4 1
1 2
2 3
3 4

输出 #3

9

输入#4

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

输出#4

91

注意

在第一个示例中,Ostap 必须将两个顶点都涂成黑色。

在第二个示例中,仅绘制两个顶点之一就足够了,因此答案为 3:Ostap 只能绘制顶点 1,只能绘制顶点 2,顶点 1 和 2 都可以。

在第三个示例中,绘制顶点的有效方法为:{1, 3}、{1, 4}、{2, 3}、{2, 4}、{1, 2, 3}、{1, 2, 4}、{1, 3, 4}、{2, 3, 4}、{1, 2, 3, 4}。