题目描述

给定一棵有 $N$ 个顶点的无向树，顶点编号为 $1,2,\ldots,N$。记 $d(u,v)$ 为顶点 $u$ 与 $v$ 之间的简单路径包含的边数，特别地，$d(u,u)=0$。

对于正整数 $K$，若 $1,2,\ldots,N$ 的排列 $p_1,p_2,\ldots,p_N$ 同时满足以下条件，则称其为好排列：

• 对所有 $2\le i\le N$，有 $d(p_{i-1},p_i)\le K$。
• 对所有 $1\le i<j\le N$，有 $d(1,p_i)\le d(1,p_j)$，即排列中顶点到顶点 $1$ 的距离非递减。

记好排列的数量为 $f(K)$。给定 $Q$ 个正整数 $K_1,K_2,\ldots,K_Q$，依次求出 $f(K_1),f(K_2),\ldots,f(K_Q)$ 对 $10^9+7$ 取模的结果。

输入格式

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

对于每组测试用例：

• 第一行包含两个整数 $N,Q$。
• 接下来 $N-1$ 行，每行包含两个整数 $u,v$，表示树中连接顶点 $u$ 和 $v$ 的一条无向边。保证这些边构成一棵树。
• 最后一行包含 $Q$ 个整数 $K_1,K_2,\ldots,K_Q$。

输出格式

对于每组测试用例输出一行，包含 $Q$ 个整数，依次为 $f(K_1),f(K_2),\ldots,f(K_Q)$ 对 $10^9+7$ 取模后的结果。

数据范围

对于所有输入：

• $1\le T\le5\times10^5$。
• $1\le Q\le N\le5\times10^5$。
• $1\le u,v\le N$，$1\le K_i\le N$。
• 一个输入文件内，所有测试用例的 $N$ 之和不超过 $5\times10^5$。

子任务

编号	分值	缩减范围
1	8	$\sum N\le10$
2	12	$Q\le\min(2,N)$ $K_i\le\min(2,N)$
3	20	$\sum N\le3000$ $Q\le\min(5,N)$
4–5	60	—

样例 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

0 2 2
0 6 12

样例 1 说明

第一棵树中，深度非递减的排列只有 $[1,2,3]$ 和 $[1,3,2]$。两者最后相邻的两个顶点距离均为 $2$，所以 $K=1$ 时均不合法，$K=2,3$ 时均合法。

第二棵树中，顶点 $2,3$ 必须排在顶点 $4,5,6$ 之前。$K=2$ 时，顶点 $2$ 不能直接接到 $4,5,6$ 中的任何一个，因此前面只能排成 $[1,2,3]$，最后三个顶点有 $6$ 种顺序。$K=3$ 时，$2,3$ 的两种顺序都可使用，共有 $12$ 种好排列。