← 返回题目列表

Codeforces · 2231/E

E. 图形切割

中文机器翻译题面 查看原题

在生日那天,小费迪亚收到了一棵有 $$$n$$$ 顶点的树和一把电锯。他想从中剪出一个连通的子图。 Fedya 决定执行以下操作:他选择三个不同的顶点 $$$a、b、c$$$ ($$$a \lt b \lt c$$$),并剪出包含所有三个顶点的最小连通子图。他希望结果子图的大小为 正是 $$$d$$$(即,剪切子图中的顶点数必须等于$$$d$$$)。

他开始对他可以剪出多少个不同的此类子图感兴趣。如果选择的顶点三元组不同,则子图被认为是不同的。帮他解决这个问题吧!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$3 \le d \leq n \le 2000$$$) - 树中的顶点数和剪切子图的所需大小。

然后是 $$$n - 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),表示相应边连接的顶点。保证给定的图是一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,输出一个数字——Fedya 可以剪切的不同子图的数量。

示例

输入
复制

3
4 3
1 2
3 1
4 1
5 5
1 2
2 4
2 3
5 1
7 7
1 2
1 3
2 4
2 5
3 6
3 7

输出
复制

3
1
0

注意

这是第一个测试用例的树的样子:

以下三元组是合适的:($$$1, 2, 3$$$)、($$$1, 2, 4$$$)、($$$1, 3, 4$$$)。但对于三元组 ($$$2, 3, 4$$$),连通子图的大小为 $$$4$$$。

这是第二个测试用例的树的样子:

对于它来说,只有三重顶点 ($$$3, 4, 5$$$) 是合适的。

这是第三个测试用例的树的样子:

可以证明没有三元组适合该子图。