CF2167F 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|$ 的值。

令 $f(i) = |S_i|$。 以第三个样例为例： - 根是 $1$ 时，只能得到 $1$ 和 $2$ 两个节点。例如，选择节点 $4, 5, 6$，$LCA(4, 5, 6) = 1$；选择节点 $2, 4, 5$，$LCA(2, 4, 5) = 2$。所以 $f(1) = 2$。 - 根是 $2$ 时，只能得到 $1$ 和 $2$ 两个节点。例如，选择节点 $1, 3, 6$，$LCA(1, 3, 6) = 1$；选择节点 $1, 4, 5$，$LCA(1, 4, 5) = 2$。所以 $f(2) = 2$。 - 根是 $3$ 时，$f(3) = 3$。例如，选择节点 $2, 4, 6$，$LCA(2, 4, 6) = 3$。 - 根是 $4$ 时，$f(4) = 3$。例如，选择节点 $2, 1, 3, 5$，$LCA(1, 3, 5) = 2$。 - 根是 $5$ 时，$f(5) = 3$。例如，选择节点 $2, 3, 4, 6$，$LCA(3, 4, 6) = 2$。 - 根是 $6$ 时，$f(6) = 4$。例如，选择节点 $3, 4, 5$，$LCA(3, 4, 5) = 2$。 所以 $2 + 2 + 3 + 3 + 3 + 4 = 17$。 由 ChatGPT 5 翻译