#5751. 「CCO 2026」Tree Traversals

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

译自 CCO 2026 Day2 T2「Tree Traversals」。

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, \dots, N$ 组成的排列 $p_1, \dots, p_N$ 如果满足以下所有条件，则被称为“好排列”：

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

那么，$f(K)$ 即为好排列的总数。

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

提示：$\bmod$ 对应于大多数编程语言中的 $\%$ 运算符，表示除法后的余数。例如，$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, \dots, K_Q$，表示 $Q$ 次询问。

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

输出格式

对于每个测试用例，输出一行包含 $Q$ 个由空格隔开的整数，即 $f(K_1), f(K_2), \dots, 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

样例输入中的两棵树如下图所示：

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

$$d\left(1, p_1\right)=1 \not \leq 0=d\left(1, p_2\right)$$

违反了第二个条件。

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

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

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	$\sum N$ 限制	$Q$ 限制	$K_i$ 限制
$1$	$8$	$1 \le \sum N \le 10$	$1 \le Q \le N$	$1 \le K_i \le N$
$2$	$12$	$1 \le \sum N \le 5 \times 10^5$	$1 \le Q \le \min(2, N)$	$1 \le K_i \le \min(2, N)$
$3$	$20$	$1 \le \sum N \le 3000$	$1 \le Q \le \min(5, N)$	$1 \le K_i \le N$
$4$	$28$	$1 \le \sum N \le 5 \times 10^5$	$1 \le Q \le N$
$5$	$32$