← 返回题目列表

Codeforces · 1691/F

F. K 集树

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

给你一棵树 $$$G$$$,有 $$$n$$$ 个顶点和一个整数 $$$k$$$。树的顶点编号从 $$$1$$$ 到 $$$n$$$。

对于顶点 $$$r$$$ 和 $$$G$$$ 的顶点子集 $$$S$$$,使得 $$$|S| = k$$$,我们将 $$$f(r, S)$$$ 定义为当树以 $$$r$$$ 为根时,包含 $$$S$$$ 中所有顶点的最小有根子树的大小。一组顶点 $$$T$$$ 称为有根子树,如果 $$$T$$$ 中的所有顶点都是连接的,并且对于 $$$T$$$ 中的每个顶点,其所有后代都属于 $$$T$$$。

您需要计算顶点 $$$r$$$ 和子集 $$$S$$$ 的所有可能不同组合的 $$$f(r, S)$$$ 之和,其中 $$$|S| = k$$$。正式地,计算以下: $$$$$$\sum_{r \in V} \sum_{S \subseteq V, |S| = k} f(r, S),$$$$$$ 其中 $$$V$$$ 是 $$$G$$$ 中的顶点集。

输出对 $$$10^9 + 7$$$ 取模的答案。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$)。

以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$),表示顶点 $$$x$$$ 和 $$$y$$$ 之间的一条边。

保证给定的边形成一棵树。

输出

打印以 $$$10^9 + 7$$$ 为模的答案。

示例

输入 #1

3 2
1 2
1 3

输出 #1

25

输入 #2

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

输出 #2

849

注意

第二个示例中的树如下所示:

在给定的树中,我们有 $$$21$$$ 大小为 $$$2$$$ 的子集。因此,$$$$$$S \in \left\{\{1, 2\}、\{1, 3\}、\{1, 4\}、\{1, 5\}、\{1, 6\}、\{1, 7\}、\{2, 3\}、\{2, 4\}、\{2, 5\}、\{2, 6\}、\{2, 7\}、 \{3, 4\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{4, 5\}, \{4, 6\}, \{4, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\} \right\}.$$$$$$ 由于我们有 $$$7$$$ 个顶点, $$$1 \le r \le 7$$$。我们需要找到所有可能的 $$$r$$$ 和 $$$S$$$ 对的 $$$f(r, S)$$$ 之和。

下面我们列出了 $$$f(r, S)$$$ 对于 $$$r$$$ 和 $$$S$$$ 的某些组合的值。

- $$$r = 1$$$,$$$S = \{3, 7\}$$$。 $$$f(r, S)$$$的值为$$$5$$$,对应的子树为$$$\{2, 3, 4, 6, 7\}$$$。
- $$$r = 1$$$,$$$S = \{5, 4\}$$$。 $$$f(r, S)$$$的值为$$$7$$$,对应的子树为$$$\{1, 2, 3, 4, 5, 6, 7\}$$$。
- $$$r = 1$$$,$$$S = \{4, 6\}$$$。 $$$f(r, S)$$$ 的值为$$$3$$$,对应的子树为$$$\{4, 6, 7\}$$$。