Canadian Computing Olympiad 2026: Day 2, Problem 2

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 \leq u, v \leq 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 \leq u \leq N~.

A permutation ~p_1, \dots, p_N~ of ~1, \dots, N~ is good if all of the following conditions are satisfied.

• ~d(p_{i - 1}, p_i) \leq K~ for all ~i = 2, \dots, N~.

• ~d(1, p_i) \leq d(1, p_j)~ for all pairs of integers ~(i, j)~ with ~1 \leq i < j \leq 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, \dots, K_Q~. He asks you to print the values of ~f(K_1), f(K_2), \dots, f(K_Q)~, mod ~10^9 + 7~.

It may also be useful to note that ~\bmod~ corresponds to the % operator in most programming languages, indicating the remainder after division. For example, ~5 \bmod 3 = 2~ and ~17 \bmod 4 = 1~.

Input Specification

Each test has multiple test cases.

The first line of the test contains one integer ~T~ (~1 \leq T \leq 5 \times 10^5~) — the number of test cases.

The first line of each test case contains two space-separated integers ~N, Q~ (~1 \leq Q \leq N \leq 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, \dots, 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~.

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 \leq \sum N \leq 10~	~1 \leq Q \leq N~	~1 \leq K_i \leq N~
3 marks	~1 \leq \sum N \leq 5 \times 10^5~	~1 \leq Q \leq \min(2, N)~	~1 \leq K_i \leq \min(2, N)~
5 marks	~1 \leq \sum N \leq 3\,000~	~1 \leq Q \leq \min(5, N)~	~1 \leq K_i \leq N~
7 marks	~1 \leq \sum N \leq 5 \times 10^5~
8 marks		~1 \leq Q \leq N~

Output Specification

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

Sample Input

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

Sample Output

0 2 2
0 6 12

Explanation for Sample Output

The two trees in the sample input are shown below.

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 $$\displaystyle d(1, p_1) = 1 \not\leq 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 \not\leq 2~.