题目描述

给定一棵有 $n$ 个节点的树，以及一个整数 $k$。

对于一个选定的根 $r$，考虑树以 $r$ 为根时的形态。现在从树中选择任意 $k$ 个互不相同的节点，求这 $k$ 个节点的最近公共祖先 LCA。

令 $S_r$ 表示：在根为 $r$ 时，所有可能选出的 $k$ 个节点集合对应的 LCA 所形成的不同节点集合。

根为 $r$ 时，这棵树的可爱度定义为 $|S_r|$。

请计算所有根的可爱度之和：

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据第一行包含两个整数 $n,k$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上的一条边。

保证输入的边构成一棵树，且所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示所有根的可爱度之和。

样例

4
2 2
1 2
5 3
1 2
1 3
1 4
1 5
6 3
1 2
1 3
2 4
2 5
3 6
10 5
5 6
4 9
3 9
2 6
2 8
8 9
6 10
1 6
4 7

2
9
17
35

样例说明

令 $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$，例如选择节点 $2,4,6$ 可以得到 $LCA(2,4,6)=3$；
• 根为 $4$ 时，$f(4)=3$，例如选择节点 $1,3,5$ 可以得到节点 $2$；
• 根为 $5$ 时，$f(5)=3$，例如选择节点 $3,4,6$ 可以得到节点 $2$；
• 根为 $6$ 时，$f(6)=4$，例如选择节点 $3,4,5$ 可以得到节点 $2$。

因此答案为 $2+2+3+3+3+4=17$。

数据范围

• $1 \le t \le 10^4$
• $2 \le k \le n \le 2\cdot 10^5$
• $1 \le u,v \le n$
• 所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$

来源

Codeforces Round 1062 (Div. 4), Problem F - Tree, TREE!!!