CF2231E.Graph Cutting

For his birthday, young Fedya was given a tree with $n$ vertices and a chainsaw. He wants to cut out a connected subgraph from it. Fedya decided to act as follows: he chooses three distinct vertices $a, b, c$ ($a \lt b \lt c$), and cuts out the minimal connected subgraph containing all three vertices. He wants the size of the resulting subgraph to be exactly $d$ (that is, the number of vertices in the cut-out subgraph must be equal to $d$).

He became interested in how many different such subgraphs he can cut out. Subgraphs are considered different if the chosen triples of vertices are different. Help him solve this problem!

为了庆祝生日，小费佳得到了一棵包含 $n$ 个顶点的树和一把链锯。他想从中切下一块连通子图。费佳决定按如下方式操作：他选择三个互不相同的顶点 $a, b, c$（满足 $a \lt b \lt c$），并切下包含这三个顶点的最小连通子图。他希望所得子图的大小恰好为 $d$（即切下的子图中顶点数必须等于 $d$）。

他开始好奇：自己一共能切出多少个不同的此类子图？若所选的顶点三元组不同，则认为对应的子图也不同。请帮助他解决这个问题！

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $d$ ($3 \le d \leq n \le 2000$) — the number of vertices in the tree and the desired size of the cut-out subgraph.

Then follow $n - 1$ lines, each containing two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$), meaning the vertices connected by the corresponding edge. It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

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

For each test case, output a single number — the number of different subgraphs that Fedya can cut out.

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

This is what the tree looks like for the first test case:

The following triples are suitable: ($1, 2, 3$), ($1, 2, 4$), ($1, 3, 4$). But for the triple ($2, 3, 4$), the size of the connected subgraph is $4$.

This is what the tree looks like for the second test case:

For it, only the triple of vertices ($3, 4, 5$) is suitable.

This is what the tree looks like for the third test case:

It can be shown that no triple is suitable for this subgraph.

第一个测试用例对应的树结构如下：

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

第二个测试用例对应的树结构如下：

对该树而言，唯一合法的顶点三元组是 ($3, 4, 5$)。

第三个测试用例对应的树结构如下：

可以证明，该子图不存在任何合法的三元组。