perm

题目描述

Yevin Kang 有一棵包含 $N$ 个顶点的树，顶点编号为 $1,2,\dots,N$。树是一个不含环的无向连通图。

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

给定一个正整数 $K$。如果 $1,2,\dots,N$ 的一个排列 $p_1,p_2,\dots,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)$。

令 $f(K)$ 表示好排列的数量。

现在给定 $Q$ 个正整数 $K_1,K_2,\dots,K_Q$，请依次求出 $f(K_1),f(K_2),\dots,f(K_Q)$，答案对 $10^9+7$ 取模。

输入格式

输入包含多组测试用例。

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

对于每组测试用例：

• 第一行包含两个整数 $N,Q$；
• 接下来 $N-1$ 行，每行包含两个整数 $u,v$，表示树上有一条连接顶点 $u$ 和 $v$ 的边；
• 最后一行包含 $Q$ 个整数 $K_1,K_2,\dots,K_Q$。

保证给出的 $N-1$ 条边构成一棵树。

输出格式

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

输入输出样例 #1

输入 #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

说明/提示

在第一组测试用例中，当 $K=2$ 或 $K=3$ 时，$[1,2,3]$ 和 $[1,3,2]$ 都是好排列。排列 $[2,1,3]$ 对任何 $K$ 都不是好排列，因为它不满足到顶点 $1$ 的距离非递减这一条件。可以证明，当 $K=1$ 时不存在好排列。

在第二组测试用例中，$[1,3,2,4,5,6]$ 是 $K=3$ 时的好排列，但不是 $K=2$ 时的好排列，因为 $d(2,4)=3>2$。

数据范围

• $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$。

子任务

附加文件