题目描述

给定一棵 $n$ 个点的树和目标大小 $d$。

选择三个不同的点 $a<b<c$。考虑包含这三个点的最小连通子图，要求该子图恰好包含 $d$ 个点。

统计满足条件的三元组数量。

输入格式

每个测试包含多组测试数据。

第一行包含整数 $t$（$1 \le t \le 500$）。

每组测试数据第一行包含两个整数 $n,d$（$3 \le d \le n \le 2000$），分别表示树的点数和目标子图大小。

接下来 $n-1$ 行，每行包含两个整数 $u,v$（$1 \le u,v \le n$，$u \ne v$），表示一条边。

保证给出的图是一棵树，且所有测试数据的 $n$ 之和不超过 $2000$。

输出格式

对于每组测试数据，输出可切出的不同子图数量。

样例 1

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

约束与提示

• 时间限制：2 秒

• 内存限制：256 MB

• 原题编号：CF2231E