CF2167F.Tree, TREE!!!

Roots change, but the tree stands strong — so should your logic.

Behruzbek received a tree$^{\text{∗}}$ with $n$ nodes. For a chosen root$^{\text{†}}$ $r$, Behruzbek wants to find cuteness of the tree.

Consider every set of $k$ distinct nodes of the tree. For each such set, compute its lowest common ancestor (LCA) in the tree when it is rooted at $r$. Let $S_r$ be the set of all distinct nodes obtained this way; then cuteness of the tree is $|S_r|$, where $|S|$ means the number of distinct elements.

After discovering the cuteness of trees, Behruzbek became interested in finding the kawaiiness of the tree! Kawaiiness is defined as:

$$\\sum\_{r = 1}^{n} |S\_r| = |S\_1| + |S\_2| + \\dots + |S\_n|$$

Unfortunately, Behruzbek is feeling sleepy now. Please help Behruzbek by finding the kawaiiness of the tree!

$^{\text{∗}}$A tree is a connected graph without cycles.

$^{\text{†}}$A rooted tree is a tree where one vertex is special and called the root.

根会变化，但树依然挺立——你的逻辑亦应如此。

贝赫鲁泽克得到了一棵含 $n$ 个节点的树$^{\text{∗}}$。对于选定的根$^{\text{†}}$ $r$，贝赫鲁泽克希望计算该树的“可爱度”（cuteness）。

考虑树中所有大小为 $k$ 的互异节点集合。对每个这样的集合，计算其在以 $r$ 为根的树中的最低公共祖先（LCA）。令 $S_r$ 表示通过此方式得到的所有互异节点构成的集合；则该树的可爱度定义为 $|S_r|$，其中 $|S|$ 表示集合 $S$ 中互异元素的个数。

在发现树的可爱度后，贝赫鲁泽克开始对树的“卡哇伊度”（kawaiiness）产生了兴趣！卡哇伊度定义为：

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

不幸的是，贝赫鲁泽克现在感到困倦了。请帮助他计算这棵树的卡哇伊度！

$^{\text{∗}}$ 树是一个无环的连通图。

$^{\text{†}}$ 有根树是一棵指定某一顶点为特殊顶点（称为根）的树。

The first line contains the number of test cases $t$ ($1 \leq t \leq 10^{4}$).

The first line of each test case contains two integers $n$ and $k$ ($2 \leq k \leq n \leq 2\cdot 10^{5}$) — the number of vertices in the tree and the number of distinct integers to be chosen.

The following $n-1$ lines of each test case describe the tree. Each of the lines contains two integers $u$ and $v$ ($1 \leq u,v \leq n$, $u \ne v$) that indicate an edge between vertex $u$ and $v$. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^{5}$.

第一行包含测试用例的数量 $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}$。

For each test case, output one integer — the value of $\sum\limits_{r=1}^n |S_r|$.

对于每个测试用例，输出一个整数——即 $\sum\limits_{r=1}^n |S_r|$ 的值。

Let $f(i) = |S_i|$

For the third example:

• Root is $1$, only $1$ and $2$ nodes can be obtained. For example, we can choose: $LCA(4, 5, 6) = 1$ and $LCA(2, 4, 5) = 2$. As a result, $f(1) = 2$.

• Root is $2$, only $1$ and $2$ nodes can be obtained. For example, we can choose: $LCA(1, 3, 6) = 1$ and $LCA(1, 4, 5) = 2$. As a result, $f(2) = 2$.

• Root is $3$, $f(3) = 3$. For example, node $3$ can be obtained by choosing: $LCA(2, 4, 6) = 3$.

• Root is $4$, $f(4) = 3$. For example, node $2$ can be obtained by choosing: $LCA(1, 3, 5) = 2$.

• Root is $5$, $f(5) = 3$. For example, node $2$ can be obtained by choosing: $LCA(3, 4, 6) = 2$.

• Root is $6$, $f(6) = 4$. For example, node $3$ can be obtained by choosing: $LCA(3, 4, 5) = 2$.

Overall, $2 + 2 + 3 + 3 + 3 + 4 = 17$.

令 $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$。