Graph CuttingAI (CI翻译)
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!
Input
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$.
Output
For each test case, output a single number — the number of different subgraphs that Fedya can cut out.
Note
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.
{"titleZh":"图的切割","bodyZh":"在生日时，年幼的 Fedya 收到了一棵有 $n$ 个顶点的树和一把链锯。他想从树上锯下一棵连通子图。Fedya 决定这样做：他选择三个不同的顶点 $a, b, c$（$a \\lt b \\lt c$），然后锯下包含这三个顶点的最小连通子图。他希望得到的子图大小恰好为 $d$（也就是说，锯下的子图中的顶点数必须等于 $d$）。
他开始好奇自己能锯下多少种不同的子图。如果选择的顶点三元组不同，就认为子图不同。请帮助他解决这个问题！\n\n## 输入格式\n\n每个测试包含多组测试用例。第一行包含测试用例数 $t$（$1 \\le t \\le 500$）。接下来是各测试用例的描述。\n\n每个测试用例的第一行包含两个整数 $n$ 和 $d$（$3 \\le d \\leq n \\le 2000$）——树的顶点数，以及希望锯下的子图大小。\n\n接下来 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \\le u, v \\le n$，$u \\neq v$），表示一条边连接的两个顶点。保证给定的图是一棵树。\n\n保证所有测试用例的 $n$ 之和不超过 $2000$。\n\n## 输出格式\n\n对于每个测试用例，输出一个整数——Fedya 可以锯下的不同子图数量。\n\n## 说明\n\n第一组测试用例中的树如下图所示：\n\n\n\n以下三元组符合要求：($1, 2, 3$)、($1, 2, 4$)、($1, 3, 4$)。但是，对于三元组 ($2, 3, 4$)，其连通子图的大小为 $4$。\n\n第二组测试用例中的树如下图所示：\n\n\n\n只有顶点三元组 ($3, 4, 5$) 符合要求。\n\n第三组测试用例中的树如下图所示：\n\n\n\n可以证明，没有任何三元组符合要求。"}AI (CI翻译)
样例
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
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。