P16905 [CCO 2026] Tree Traversals

Yevin Kang has a tree with $N$ vertices that are labelled with integers from $1$ to $N$. A tree is an undirected connected graph that does not contain a cycle. Let $K$ be a positive integer. We define $f(K)$ as follows. For any two vertices $1 \le u, v \le N$, let $d(u, v)$ denote the number of edges on the simple path connecting vertex $u$ and vertex $v$. In particular, $d(u, u) = 0$ for all $1 \le u \le N$. A permutation $p_1, \ldots, p_N$ of $1, \ldots, N$ is good if all of the following conditions are satisfied. - $d(p_{i-1}, p_i) \le K$ for all $i = 2, \ldots, N$. - $d(1, p_i) \le d(1, p_j)$ for all pairs of integers $(i, j)$ with $1 \le i < j \le N$. Then, $f(K)$ is the number of good permutations. Yevin thinks this problem is too easy, so he gives you $Q$ positive integers $K_1, \ldots, K_Q$. He asks you to print the values of $f(K_1), f(K_2), \ldots, f(K_Q)$, mod $10^9 + 7$. It may also be useful to note that “mod” corresponds to the $\%$ operator in most programming languages, indicating the remainder after division. For example, $5 \bmod 3 = 2$ and $17 \bmod 4 = 1$.

Each test has multiple test cases. The first line of the test contains one integer $T$ ($1 \le T \le 5 \times 10^5$) — the number of test cases. The first line of each test case contains two space-separated integers $N, Q$ ($1 \le Q \le N \le 5 \times 10^5$). Each of the next $N - 1$ lines contains two space-separated integers $u, v$ — indicating that there is an edge connecting $u$ and $v$ in the tree. It is guaranteed that the $N - 1$ edges form a tree. The next line contains $Q$ integers, $K_1, \ldots, K_Q$ — denoting the $Q$ queries. It is guaranteed that the sum of $N$ over all test cases in a test (denoted by $\sum N$) does not exceed $5 \times 10^5$.

For each test case, output one line with $Q$ space-separated integers — the values of $f(K_1), f(K_2), \ldots, f(K_Q)$, mod $10^9 + 7$.

**Explanation of Output for Sample Input** The two trees in the sample input are shown below. :::align{center}  ::: In the first test case, for $K = 2$ or $K = 3$, both $[1, 2, 3]$ and $[1, 3, 2]$ are good permutations. $[2, 1, 3]$ is not a good permutation for all values of $K$ because $$d(1, p_1) = 1 \nleq 0 = d(1, p_2)$$ violates the second condition. It can be shown that no permutation is good for $K = 1$. In the second test case, $[1, 3, 2, 4, 5, 6]$ is a good permutation for $K = 3$ but not a good permutation for $K = 2$ because $d(2, 4) = 3 \nleq 2$. The following table shows how the $25$ available marks are distributed: | Marks Awarded | Bounds on $\sum N$ | Bounds on $Q$ | Bounds on $K_i$ | |:-:|:-:|:-:|:-:| | $2$ marks | $1 \le \sum N \le 10$ | $1 \le Q \le N$ | $1 \le K_i \le N$ | | $3$ marks | $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$ marks | $1 \le \sum N \le 3000$ | $1 \le Q \le \min(5, N)$ | $1 \le K_i \le N$ | | $7$ marks | $1 \le \sum N \le 5 \times 10^5$ | ^ | $1 \le K_i \le N$ | | $8$ marks | ^ | $1 \le Q \le N$ | ^ |