CF735E Ostap and Tree

Ostap 已经在里约热内卢郊区定居，并开始在他的花园里种植一棵树。这里的“树”指的是一张连通且无环的无向图。 Ostap 种植的这棵树现在有 $n$ 个顶点。他想将一些顶点涂成黑色，使得从任意一个顶点 $u$ 出发，距离不超过 $k$ 的范围内至少有一个黑色顶点 $v$。两个顶点间的距离指的是它们之间的最短路径经过的边数。 由于涂色方案的数目可能非常大，Ostap 希望你输出其对 $10^9+7$ 取模的结果。如果存在一个顶点在一种方案中被染成黑色，而在另一种方案中没有被染成黑色，则这两种方案被认为是不同的。

输入的第一行包含两个整数 $n$ 和 $k$（$1\leq n\leq 100$，$0\leq k\leq \min(20, n-1)$）——表示树的顶点数以及任意顶点到最近的黑色顶点的最大允许距离。注意 $k$ 的特殊约束。 接下来的 $n-1$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1\leq u_i, v_i \leq n$），表示第 $i$ 条边连接了顶点 $u_i$ 和 $v_i$。保证输入构成一棵树。

输出一个整数，表示把树染色的方案数对 $1000000007$（$10^9+7$）取模的结果。

在第一个样例中，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\}$。 由 ChatGPT 5 翻译