这是问题的困难版本。唯一的区别是在这个版本中$$$k\le n$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
克托莉和浮岛。
洛天依现在生活在一个有$$$n$$$浮岛的世界。浮岛之间由$$$n-1$$$无向航线连接,任意两个浮岛可以通过航线相互到达。这意味着,$$$n$$$ 浮岛形成一棵树。
有一天,洛天依想见见她的朋友们:Chtholly、Nephren、William、...... 总的来说,她想见见$$$k$$$人。她不知道它们的确切位置,但她知道它们位于两两不同的岛屿上。她定义一个岛屿是好的,当且仅当从它到拥有 $$$k$$$ 人的岛屿的距离 $$$^{\dagger}$$$ 的总和是所有 $$$n$$$ 岛屿中最小的。
现在,洛天依想知道,如果将$$$k$$$个人随机设置在$$$n$$$个不同的$$$k$$$个岛屿中,那么期望的好岛屿数量是多少?你只需要告诉她期望的数字模$$$10^9+7$$$。
$$$^{\dagger}$$$两个岛屿之间的距离是从一个岛屿到另一个岛屿所需的最少航线数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le k \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$$$ ($$$\operatorname{mod} M$$$)。输出等于$$$p \cdot q^{-1}$$$ $$$\operatorname{mod} M$$$的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p$$$ ($$$\operatorname{mod} M$$$)。
示例
输入 #1
4 2 1 2 2 3 3 4
输出 #1
666666674
输入 #2
5 5 1 2 2 3 3 4 3 5
输出 #2
1
注意
在第一个示例中,航线形成以下树:
如果人们在岛屿$$$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}$$$,等于 $$$666666674$$$ 模 $$$10^9+7$$$。
在第二个示例中,航线形成以下树:
我们可以看到每个岛都有一个人,只有$$$3$$$这个岛是好的。所以预期的数字是$$$1$$$。