English · Original
Chinese · Translation
Formal · Original
Ostap already settled down in Rio de Janiero suburb and started to grow a tree in his garden. Recall that a tree is a connected undirected acyclic graph.
Ostap's tree now has _n_ vertices. He wants to paint some vertices of the tree black such that from any vertex _u_ there is at least one black vertex _v_ at distance no more than _k_. Distance between two vertices of the tree is the minimum possible number of edges of the path between them.
As this number of ways to paint the tree can be large, Ostap wants you to compute it modulo 109 + 7. Two ways to paint the tree are considered different if there exists a vertex that is painted black in one way and is not painted in the other one.
## Input
The first line of the input contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 100, 0 ≤ _k_ ≤ _min_(20, _n_ - 1)) — the number of vertices in Ostap's tree and the maximum allowed distance to the nearest black vertex. **Don't miss** the unusual constraint for _k_.
Each of the next _n_ - 1 lines contain two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_) — indices of vertices, connected by the _i_\-th edge. It's guaranteed that given graph is a tree.
## Output
Print one integer — the remainder of division of the number of ways to paint the tree by 1 000 000 007 (109 + 7).
[samples]
## Note
In the first sample, Ostap has to paint both vertices black.
In the second sample, it is enough to paint only one of two vertices, thus the answer is 3: Ostap can paint only vertex 1, only vertex 2, vertices 1 and 2 both.
In the third sample, the valid ways to paint vertices are: {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}.
Ostap 已经在里约热内卢郊区安顿下来，并开始在花园里种植一棵树。回忆一下，树是一个连通的无向无环图。
Ostap 的树现在有 #cf_span[n] 个顶点。他希望将树中的一些顶点染成黑色，使得从任意顶点 #cf_span[u] 出发，都存在至少一个黑色顶点 #cf_span[v]，其距离不超过 #cf_span[k]。树中两个顶点之间的 #cf_span(class=[tex-font-style-underline], body=[Distance]) 定义为连接它们的路径上最少的边数。
由于染色方案的数量可能很大，Ostap 希望你计算其对 #cf_span[109 + 7] 取模的结果。两种染色方案被认为是不同的，当且仅当存在至少一个顶点在一种方案中被染成黑色而在另一种方案中未被染色。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ k ≤ min(20, n - 1)]）—— 分别表示 Ostap 的树中的顶点数和到最近黑色顶点的最大允许距离。*注意* 对 #cf_span[k] 的非同寻常的约束。
接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]）—— 表示第 #cf_span[i] 条边连接的两个顶点的编号。保证给出的图是一棵树。
请输出一个整数——将染色方案数对 #cf_span[1 000 000 007]（即 #cf_span[109 + 7]）取模后的余数。
在第一个样例中，Ostap 必须将两个顶点都染成黑色。
在第二个样例中，只需将两个顶点中的一个染成黑色即可，因此答案为 #cf_span[3]：Ostap 可以只染顶点 #cf_span[1]，只染顶点 #cf_span[2]，或同时染两个顶点。
在第三个样例中，合法的染色方案为：#cf_span[{1, 3}]，#cf_span[{1, 4}]，#cf_span[{2, 3}]，#cf_span[{2, 4}]，#cf_span[{1, 2, 3}]，#cf_span[{1, 2, 4}]，#cf_span[{1, 3, 4}]，#cf_span[{2, 3, 4}]，#cf_span[{1, 2, 3, 4}]。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ k ≤ min(20, n - 1)]）—— 分别表示 Ostap 的树中的顶点数和到最近黑色顶点的最大允许距离。*注意* 对 #cf_span[k] 的非同寻常的约束。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]）—— 表示第 #cf_span[i] 条边连接的两个顶点的编号。保证给出的图是一棵树。
## Output
请输出一个整数——将染色方案数对 #cf_span[1 000 000 007]（即 #cf_span[109 + 7]）取模后的余数。
[samples]
## Note
在第一个样例中，Ostap 必须将两个顶点都染成黑色。
在第二个样例中，只需将两个顶点中的一个染成黑色即可，因此答案为 #cf_span[3]：Ostap 可以只染顶点 #cf_span[1]，只染顶点 #cf_span[2]，或同时染两个顶点。
在第三个样例中，合法的染色方案为：#cf_span[{1, 3}]，#cf_span[{1, 4}]，#cf_span[{2, 3}]，#cf_span[{2, 4}]，#cf_span[{1, 2, 3}]，#cf_span[{1, 2, 4}]，#cf_span[{1, 3, 4}]，#cf_span[{2, 3, 4}]，#cf_span[{1, 2, 3, 4}]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of vertices in a tree.
Let $ k \in \mathbb{Z} $, $ 0 \leq k \leq \min(20, n-1) $, be the maximum allowed distance from any vertex to the nearest black vertex.
Let $ T = (V, E) $ be a tree with $ V = \{1, 2, \dots, n\} $ and $ |E| = n-1 $.
Let $ d(u,v) $ denote the shortest path distance (number of edges) between vertices $ u $ and $ v $.
Let $ S \subseteq V $ be a subset of black vertices.
**Constraints**
1. $ 1 \leq n \leq 100 $
2. $ 0 \leq k \leq \min(20, n-1) $
3. For every vertex $ u \in V $, there exists at least one vertex $ v \in S $ such that $ d(u,v) \leq k $.
**Objective**
Compute the number of valid subsets $ S \subseteq V $ satisfying the coverage constraint, modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "E. Ostap and Tree",
"description": {
"content": "Ostap already settled down in Rio de Janiero suburb and started to grow a tree in his garden. Recall that a tree is a connected undirected acyclic graph. Ostap's tree now has _n_ vertices. He wants t",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF735E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Ostap already settled down in Rio de Janiero suburb and started to grow a tree in his garden. Recall that a tree is a connected undirected acyclic graph.\n\nOstap's tree now has _n_ vertices. He wants t...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Ostap 已经在里约热内卢郊区安顿下来，并开始在花园里种植一棵树。回忆一下，树是一个连通的无向无环图。\n\nOstap 的树现在有 #cf_span[n] 个顶点。他希望将树中的一些顶点染成黑色，使得从任意顶点 #cf_span[u] 出发，都存在至少一个黑色顶点 #cf_span[v]，其距离不超过 #cf_span[k]。树中两个顶点之间的 #cf_span(class=[tex-font-s...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices in a tree. \nLet $ k \\in \\mathbb{Z} $, $ 0 \\leq k \\leq \\min(20, n-1) $, be the maximum allowed distance from any vertex to the ne...",
"is_translate": false,
"language": "Formal"
}
]
}