CF2231E Graph Cutting

在生日这天，小 Fedya 得到了一棵包含 $n$ 个节点的树。他希望从这棵树中截取出一个连通子图。Fedya 决定按如下方式操作：他选择三个不同的顶点 $a, b, c$（$a < b < 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$），表示树中的一条边，即两顶点 $u$ 和 $v$ 相连。保证所给图一定是一棵树。 保证所有测试用例的 $n$ 之和不超过 $2000$。

对于每个测试用例，输出一个整数，表示 Fedya 能截取得到的不同子图数量。

下图是第一个测试用例中的树：  适合的三元组有：（$1, 2, 3$）、（$1, 2, 4$）、（$1, 3, 4$）。而对于三元组（$2, 3, 4$），所截取的连通子图大小为 $4$，不满足要求。 下图是第二个测试用例中的树：  对于它，只有（$3, 4, 5$）这个三元组满足要求。 下图是第三个测试用例中的树：  可以证明没有任何三元组能满足截取出的子图大小为 $d$。 由 ChatGPT 5 翻译