题目描述

Yevin Kang 有一棵包含 $N$ 个顶点的树，顶点用 $1$ 到 $N$ 的整数标号。树是一张无向连通图，且不包含环。

令 $K$ 为一个正整数。我们如下定义 $f(K)$。

对于任意两个顶点 $1 \le u, v \le N$，令 $d(u, v)$ 表示连接顶点 $u$ 和顶点 $v$ 的简单路径上的边数。特别地，对所有 $1 \le u \le N$ 有 $d(u, u) = 0$。

一个 $1, \ldots, N$ 的排列 $p_1, \ldots, p_N$ 被称为 好的，如果满足以下所有条件。

• 对所有 $i = 2, \ldots, N$，有 $d(p_{i-1}, p_i) \le K$。
• 对所有满足 $1 \le i < j \le N$ 的整数对 $(i, j)$，有 $d(1, p_i) \le d(1, p_j)$。

那么，$f(K)$ 就是好的排列的个数。

Yevin 认为这个问题太简单了，于是他给出了 $Q$ 个正整数 $K_1, \ldots, K_Q$。他要求你输出 $f(K_1), f(K_2), \ldots, f(K_Q)$ 对 $10^9 + 7$ 取模的值。

这里可能还需要说明，“mod” 对应于大多数编程语言中的 $\%$ 运算符，表示除法取余。例如，$5 \bmod 3 = 2$ 且 $17 \bmod 4 = 1$。

输入格式

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

输入的第一行包含一个整数 $T$ ($1 \le T \le 5 \times 10^5$) —— 测试用例的数量。

每个测试用例的第一行包含两个空格分隔的整数 $N, Q$ ($1 \le Q \le N \le 5 \times 10^5$)。

接下来 $N - 1$ 行每行包含两个空格分隔的整数 $u, v$ —— 表示树中有一条连接 $u$ 和 $v$ 的边。保证这 $N - 1$ 条边构成一棵树。

接下来一行包含 $Q$ 个整数 $K_1, \ldots, K_Q$ —— 表示 $Q$ 个查询。

保证一个测试中所有测试用例的 $N$ 之和（记为 $\sum N$）不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一行包含 $Q$ 个空格分隔的整数 —— 即 $f(K_1), f(K_2), \ldots, f(K_Q)$ 对 $10^9 + 7$ 取模的值。

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

0 2 2
0 6 12

提示

样例输入输出解释

样例中的两棵树如下图所示。

:::align{center} :::

在第一个测试用例中，对于 $K = 2$ 或 $K = 3$，$[1, 2, 3]$ 和 $[1, 3, 2]$ 都是好的排列。$[2, 1, 3]$ 对所有 $K$ 的值都不是好的排列，因为

违反了第二个条件。

可以证明，当 $K = 1$ 时不存在好的排列。

在第二个测试用例中，$[1, 3, 2, 4, 5, 6]$ 对于 $K = 3$ 是一个好的排列，但对于 $K = 2$ 不是好的排列，因为 $d(2, 4) = 3 \nleq 2$。

以下表格展示了可获得的 $25$ 分的分配情况：

翻译由 DeepSeek V4 Pro 完成