CF1824B1 LuoTianyi and the Floating Islands (Easy Version)

这是该问题的简单版本。唯一的区别在于本版本中 $k\le\min(n,3)$。只有当你同时解决了两个版本的问题时，才能进行 Hack。  Chtholly 和浮空岛。LuoTianyi 现在生活在一个有 $n$ 个浮空岛的世界里。这些浮空岛通过 $n-1$ 条无向空中航线连接，任意两个岛屿都可以通过这些航线互相到达。也就是说，这 $n$ 个浮空岛构成了一棵树。 有一天，LuoTianyi 想去见她的朋友们：Chtholly、Nephren、William，等等。她一共想见 $k$ 个人。她不知道他们的具体位置，但她知道他们分别在 $k$ 个不同的岛屿上。她定义：如果某个岛屿到这 $k$ 个有人的岛屿的距离之和在所有 $n$ 个岛屿中最小，则称这个岛屿为“好岛”。 现在，LuoTianyi 想知道，如果这 $k$ 个人被随机分配到 $n$ 个岛屿中的 $k$ 个不同岛屿上，那么“好岛”的期望数量是多少？你只需要告诉她这个期望值对 $10^9+7$ 取模后的结果。 $^\dagger$ 两个岛屿之间的距离是指从一个岛屿到另一个岛屿最少需要经过的航线数量。

第一行包含两个整数 $n$ 和 $k$（$1\le k \le \min(n,3),\ 1\le n \le 2\cdot 10^5$）——分别表示岛屿数量和人数。 接下来的 $n-1$ 行描述空中航线。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i,v_i \le n,\ u_i \neq v_i$），表示第 $i$ 条航线连接的两个岛屿。

输出一个整数，表示“好岛”的期望数量对 $10^9+7$ 取模后的结果。 形式化地说，设 $M=10^9+7$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0\pmod{M}$。输出满足 $0\le x

在第一个样例中，航线构成如下的树：  如果这两个人分别在岛屿 $1$ 和 $2$ 上，则岛屿 $1$ 和 $2$ 都是好岛。 从岛屿 $1$ 或 $2$ 到所有有人的岛屿的距离和为 $1+0=1$，这是最小值。而从岛屿 $3$ 到所有有人的岛屿的距离和为 $2+1=3$，大于 $1$。 类似地，当两个人在岛屿 $1$ 和 $3$ 时，岛屿 $1,2,3$ 都是好岛。 当两个人在岛屿 $1$ 和 $4$ 时，岛屿 $1,2,3,4$ 都是好岛。 当两个人在岛屿 $2$ 和 $3$ 时，岛屿 $2$ 和 $3$ 都是好岛。 当两个人在岛屿 $2$ 和 $4$ 时，岛屿 $2,3,4$ 都是好岛。 当两个人在岛屿 $3$ 和 $4$ 时，岛屿 $3$ 和 $4$ 都是好岛。 所以“好岛”数量的期望为 $\frac{16}{6}$，对 $10^9+7$ 取模后等于 $666666674$。 在第二个样例中，航线构成如下的树：  总是只有一个好岛，所以期望值为 $1$。 由 ChatGPT 4.1 翻译