P16905 [CCO 2026] 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, \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$ 取模的值。

**样例输入输出解释** 样例中的两棵树如下图所示。 :::align{center}  ::: 在第一个测试用例中，对于 $K = 2$ 或 $K = 3$，$[1, 2, 3]$ 和 $[1, 3, 2]$ 都是好的排列。$[2, 1, 3]$ 对所有 $K$ 的值都不是好的排列，因为 $$d(1, p_1) = 1 \nleq 0 = d(1, p_2)$$ 违反了第二个条件。 可以证明，当 $K = 1$ 时不存在好的排列。 在第二个测试用例中，$[1, 3, 2, 4, 5, 6]$ 对于 $K = 3$ 是一个好的排列，但对于 $K = 2$ 不是好的排列，因为 $d(2, 4) = 3 \nleq 2$。 以下表格展示了可获得的 $25$ 分的分配情况： | 分值 | $\sum N$ 的限制 | $Q$ 的限制 | $K_i$ 的限制 | |:-:|:-:|:-:|:-:| | $2$ 分 | $1 \le \sum N \le 10$ | $1 \le Q \le N$ | $1 \le K_i \le N$ | | $3$ 分 | $1 \le \sum N \le 5 \times 10^5$ | $1 \le Q \le \min(2, N)$ | $1 \le K_i \le \min(2, N)$ | | $5$ 分 | $1 \le \sum N \le 3000$ | $1 \le Q \le \min(5, N)$ | $1 \le K_i \le N$ | | $7$ 分 | $1 \le \sum N \le 5 \times 10^5$ | ^ | ^ | | $8$ 分 | ^ | $1 \le Q \le N$ | ^ | 翻译由 DeepSeek V4 Pro 完成