A16743 | Tree, TREE!!!

树根可以变化，但树始终坚定如初——你的逻辑也应当如此坚韧。

Behruzbek 得到了一棵 $n$ 个节点的树 $ ^{\text{∗}}$。对于一个选定的根节点 $r$ $^{\text{†}}$，Behruzbek 想要计算这棵树的可爱度（cuteness）。

考虑树上所有选取 $k$ 个不同节点的集合。对于每一个这样的集合，计算在以 $r$ 为根时，它们的最近公共祖先（[LCA](https://en.wikipedia.org/wiki/Lowest_common_ancestor)）。设 $S_r$ 是所有通过上述操作得到的不重复节点的集合，那么，树的可爱度就是 $|S_r|$，即集合中不同节点的个数。

在发现树的可爱度之后，Behruzbek 对树的 "kawaiiness" 感兴趣起来！"Kawaiiness" 定义为：

$$ \sum_{r = 1}^{n} |S_r| = |S_1| + |S_2| + \dots + |S_n| $$

但现在 Behruzbek 感到困倦。请帮他计算这棵树的 "kawaiiness"！

$^{\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|$ 的值。