Water on Tree

Water on Tree

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

Friendship is one of the most precious things in the world. A true friendship is never broken. This kind of friendship suits Roy and his friend Hridoy. A few days ago, Hridoy faced a problem. The problem is very simple,

You are given a tree with N nodes. The root of the tree is 1. Intially, root node 1 fills up with the infinity-level water supply, and all other nodes are empty. Water flow starts at root node 1, and it takes exactly one second to reach any neighboring nodes.

You are also given Q query; in each query, you need to determine within X seconds how many nodes are filled up by water.

Unfortunately, Roy is busy with his assignment. As a well-wisher for Roy, can you solve this problem?

Input

First Line T, number of test cases.
In each test case,
First Line,N the number of nodes of the tree and Q the number of query.
Second Line, Exactly N-1 Edges, Between U and V.
Thrid Line, In each query an integer X.

\(1 <= T <= 1000\)
\(1 <= N ,Q , X <= 10^5\)
\(1 <= U , V <= N\)

It's gurantee that graph is a tree.
Sum of N and Q, over all test cases doesn't exceed \(2 * 10^5\).

Output

In each query, print the answer with a newline.

Sample

Input Output
1
5 5
1 2
2 3
3 4
1 5
1
2
3
4
5
3
4
5
5
5

Sample test case explaination:

Brain Booster #3

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
9
Start at
2024-05-06 15:00
End at
2024-05-06 18:00
Duration
3.0 hour(s)
Host
Partic.
91