题目描述

有 $N$ 个地点，编号为 $1,2,\ldots,N$，这些地点通过 $N-1$ 条双向道路连通。

记两个地点 $u,v$ 之间的道路条数为 $d(u,v)$，现在要安排一次长度为$N$的巡路顺序

$$p_1,p_2,\ldots,p_N.$$

从$p_1$出发，$p_N$结束，满足每个地点恰好经过一次。

巡路时要求对于任意 $1\le i<j\le N$，都要满足：

$$d(1,p_i)\le d(1,p_j).$$

给定一个正整数 $K$。如果一个巡路顺序对任意$1 \leq i <N$还满足：

$$d(p_i,p_{i+1})\le K,$$

那么称它是一个合法的 $K$-巡路顺序。

记 $F(K)$ 为合法的 $K$-巡路顺序数量。你需要对每个询问的 $K$，输出 $F(K)$ 对 $10^9+7$ 取模后的值。

输入格式

每个测试文件包含多个测试用例。

第一行包含一个整数 $T$，表示测试用例数。

对于每个测试用例：

• 第一行包含两个整数 $N,Q$；
• 接下来 $N-1$ 行，每行包含两个整数 $u,v$，表示 $u$ 与 $v$ 之间有一条边；
• 最后一行包含 $Q$ 个整数 $K_1,K_2,\ldots,K_Q$。

输出格式

对于每个测试用例，输出一行 $Q$ 个空格分隔的整数，第 $i$ 个整数为

$$F(K_i)\bmod (10^9+7).$$

样例1输入

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

样例1输出

0 2 2
0 6 12

样例1解释

第一组数据中，离 $1$ 号地点最近的是地点 $1$ 本身，地点 $2,3$ 到地点 $1$ 的距离相同。因此巡路顺序只能先访问 $1$，再访问 $2,3$ 的某种顺序。

当 $K=1$ 时，最后两次访问的地点之间距离为 $2$，没有顺序合法；当 $K\ge 2$ 时，$[1,2,3]$ 与 $[1,3,2]$ 都合法，答案为 $2$。

第二组数据中，同样距离的地点有多种排列方式，但相邻访问地点之间的距离会随排列变化，所以 $K=2$ 和 $K=3$ 的答案不同。

样例2

见选手目录下的 layers/layers2.in 与 layers/layers2.ans。

该样例满足子任务 $1$ 的约束条件。

样例3

见选手目录下的 layers/layers3.in 与 layers/layers3.ans。

该样例满足子任务 $2$ 的约束条件。

样例4

见选手目录下的 layers/layers4.in 与 layers/layers4.ans。

该样例满足子任务 $3$ 的约束条件。

样例5

见选手目录下的 layers/layers5.in 与 layers/layers5.ans。

该样例满足子任务 $4$ 的约束条件。

样例6

见选手目录下的 layers/layers6.in 与 layers/layers6.ans。

该样例满足子任务 $5$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1\le T\le 5\times 10^5$；
• $1\le Q\le N\le 5\times 10^5$；
• $1\le K_i\le N$；
• 每个测试文件中所有测试用例的 $N$ 之和不超过 $5\times 10^5$；
• 输入的 $N-1$ 条边构成一棵树。

子任务编号	分值	约束条件
$1$	$10$	$\sum N\le 10$
$2$	$15$	$Q\le 2$ 且 $K_i\le 2$
$3$	$25$	$\sum N\le 3000$ 且 $Q\le 5$
$4$	$22$	$Q\le 5$
$5$	$28$	无额外限制

本题采用捆绑测试。每个子任务内的测试点必须全部通过，才能获得该子任务分数。