Behruzbek 收到 一棵树$$$^{\text{*}}$$$ 与 $$$n$$$ 节点。对于一个选择的 根$$$^{\text{†}}$$$ $$$r$$$,Behruzbek 想要找到 可爱 树的 。
考虑树中每组$$$k$$$ 不同的节点。对于每个这样的集合,计算其 最低共同祖先 (LCA) 在树中,当它的根位于 $$$r$$$ 时。令 $$$S_r$$$ 为通过这种方式获得的所有不同节点的集合;那么 树的 可爱 树的 是 $$$|S_r|$$$,其中 $$$|S|$$$ 表示不同元素的数量。
发现后 可爱 树的 的树木,Behruzbek 开始对寻找 可爱 树的! 卡哇伊 定义为:
$$\sum_{r = 1}^{n} |S_r| = |S_1| + |S_2| + \点 + |S_n|$$
不幸的是,Behruzbek 现在感到困倦。请帮助 Behruzbek 找到 可爱 树的!
$$$^{\text{*}}$$$树是没有环的连通图。
$$$^{\text{†}}$$$有根树是一棵树,其中一个顶点是特殊的,称为根。
输入
第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$)。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq k \leq n \leq 2\cdot 10^{5}$$$) — 树中的顶点数量和要选择的不同整数的数量。
每个测试用例的以下 $$$n-1$$$ 行描述了树。每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u,v \leq n$$$, $$$u \ne v$$$),表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证这些边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^{5}$$$。
输出
对于每个测试用例,输出一个整数 - $$$\sum\limits_{r=1}^n |S_r|$$$ 的值。
示例
输入复制
42 21 25 31 21 31 41 56 31 21 32 42 53 610 55 64 93 92 62 88 96 101 64 7
输出复制
291735
注意
让 $$$f(i) = |S_i|$$$
对于第三个示例:
- 根为$$$1$$$,只能得到$$$1$$$和$$$2$$$节点。例如,我们可以选择:$$$LCA(4, 5, 6) = 1$$$ 和 $$$LCA(2, 4, 5) = 2$$$。结果,$$$f(1) = 2$$$。
- 根为$$$2$$$,只能得到$$$1$$$和$$$2$$$节点。例如,我们可以选择:$$$LCA(1, 3, 6) = 1$$$ 和 $$$LCA(1, 4, 5) = 2$$$。结果,$$$f(2) = 2$$$。
- 根是$$$3$$$,$$$f(3) = 3$$$。例如,节点$$$3$$$可以通过选择:$$$LCA(2,4,6) = 3$$$来获得。
- 根是$$$4$$$,$$$f(4) = 3$$$。例如,节点$$$2$$$可以通过选择:$$$LCA(1, 3, 5) = 2$$$来获得。
- 根是$$$5$$$,$$$f(5) = 3$$$。例如,节点 $$$2$$$ 可以通过选择:$$$LCA(3, 4, 6) = 2$$$ 来获得。
- 根是$$$6$$$,$$$f(6) = 4$$$。例如,节点 $$$3$$$ 可以通过选择:$$$LCA(3, 4, 5) = 2$$$ 来获得。
总的来说,$$$2 + 2 + 3 + 3 + 3 + 4 = 17$$$。