CF1691F.K-Set Tree

You are given a tree $G$ with $n$ vertices and an integer $k$. The vertices of the tree are numbered from $1$ to $n$.

For a vertex $r$ and a subset $S$ of vertices of $G$, such that $|S| = k$, we define $f(r, S)$ as the size of the smallest rooted subtree containing all vertices in $S$ when the tree is rooted at $r$. A set of vertices $T$ is called a rooted subtree, if all the vertices in $T$ are connected, and for each vertex in $T$, all its descendants belong to $T$.

You need to calculate the sum of $f(r, S)$ over all possible distinct combinations of vertices $r$ and subsets $S$, where $|S| = k$. Formally, compute the following: $$\sum_{r \in V} \sum_{S \subseteq V, |S| = k} f(r, S),$$ where $V$ is the set of vertices in $G$.

Output the answer modulo $10^9 + 7$.

给你一棵包含 $n$ 个顶点的树 $G$ 和一个整数 $k$。树的顶点编号为 $1$ 到 $n$。

对于一个顶点 $r$ 和 $G$ 的一个顶点子集 $S$（满足 $|S| = k$），我们定义 $f(r, S)$ 为：当以 $r$ 为根时，包含 $S$ 中所有顶点的最小有根子树的大小。一个顶点集合 $T$ 被称为有根子树，当且仅当 $T$ 中的所有顶点连通，且对 $T$ 中的每个顶点，其所有后代也均属于 $T$。

你需要计算所有可能的顶点 $r$ 与所有满足 $|S| = k$ 的不同子集 $S$ 对应的 $f(r, S)$ 之和。形式化地，计算下式：

$$\sum_{r \in V} \sum_{S \subseteq V,\, |S| = k} f(r, S),$$

其中 $V$ 是树 $G$ 的顶点集。

输出结果对 $10^9 + 7$ 取模。

The first line contains two integers $n$ and $k$ ($3 \le n \le 2 \cdot 10^5$, $1 \le k \le n$).

Each of the following $n - 1$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$), denoting an edge between vertex $x$ and $y$.

It is guaranteed that the given edges form a tree.

第一行包含两个整数 $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$ 之间的一条边。

保证所给的边构成一棵树。

Print the answer modulo $10^9 + 7$.

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

The tree in the second example is given below:

We have $21$ subsets of size $2$ in the given tree. Hence, $$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\}.$$ And since we have $7$ vertices, $1 \le r \le 7$. We need to find the sum of $f(r, S)$ over all possible pairs of $r$ and $S$.

Below we have listed the value of $f(r, S)$ for some combinations of $r$ and $S$.

• $r = 1$, $S = {3, 7}$. The value of $f(r, S)$ is $5$ and the corresponding subtree is ${2, 3, 4, 6, 7}$.
• $r = 1$, $S = {5, 4}$. The value of $f(r, S)$ is $7$ and the corresponding subtree is ${1, 2, 3, 4, 5, 6, 7}$.
• $r = 1$, $S = {4, 6}$. The value of $f(r, S)$ is $3$ and the corresponding subtree is ${4, 6, 7}$.

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

给定树中大小为 $2$ 的子集共有 $21$ 个。因此，

$$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)$ 的总和。

下面列出了若干组 $(r, S)$ 对应的 $f(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\}$。