E. Innopolis Data Center
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the data center of the University of Innopolis there are $$$n$$$ servers numbered with consecutive integers from $$$1$$$ to $$$n$$$. The servers are connected by $$$n - 1$$$ optical fiber cables in such a way that data transmission is possible between any two servers through one or multiple cables. In other words, the connections between servers form a tree.

Each optical fiber cable transmits data with a delay of $$$1$$$ unit of time, and the delay between two servers is equal to the distance in the tree between these servers.

It is required to select several servers for a distributed data storage system in such a way that the delay between any two servers in the system does not exceed $$$d$$$. Let the selected servers be $$$s_1, s_2, \ldots, s_k$$$, then the total delay of the system is the sum of delays between all $$$\frac{k (k - 1)}{2}$$$ pairs of servers $$$s_i$$$. Formally:

  1. $$$\mathtt{dist}(s_i, s_j) \le d$$$ must hold for any $$$i$$$ and $$$j$$$ (where $$$\mathtt{dist}$$$ is their distance in the tree);
  2. then the total delay of the system is $$$\sum\limits_{i \lt j} \mathtt{dist}(s_i, s_j)$$$.

Your task is to answer $$$q$$$ queries. Each query is defined by a number of a server $$$u$$$ and represents the following question: if a specific server $$$u$$$ is included in the data storage system, what is the maximum possible total delay of the system?

Input

The first line of the input contains two integers $$$n$$$ and $$$d$$$ — the number of servers in the data center and the maximum allowed delay between two servers ($$$2 \le n \le 5 \cdot 10^5$$$; $$$0 \le d \le n - 1$$$).

Each of the next $$$n - 1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ — the numbers of two servers directly connected by the $$$i$$$-th optical cable ($$$1 \le a_i, b_i \le n$$$). It is guaranteed that it's possible to transmit data between any two servers through one or multiple consecutive cables.

The next line contains a single integer $$$q$$$ — the number of queries ($$$1 \le q \le 10$$$). In the $$$i$$$-th of the next $$$q$$$ lines, a single integer $$$u_i$$$ is given — the number of the server from the $$$i$$$-th query ($$$1 \le u_i \le n$$$).

Output

For each query, output a single integer on a separate line — the maximum total delay of the system when the corresponding server is included in the data storage system.

Scoring

Points for each subtask from 1 to 4 are awarded only if all tests for this subtask and the necessary subtasks are successfully passed.

Each test in subtasks 5 and 6 is scored independently and costs 3 points in subtask 5 or 2 points in subtask 6.

SubtaskPointsConstraints Necessary subtasks Feedback policy
0–examplesfull
112$$$n \le 15$$$0first error
211$$$d = n - 1$$$first error
313$$$n \le 300$$$0, 1first error
416$$$n \le 5000$$$0, 1, 3first error
5$$$8 \times 3$$$$$$n \le 10^5$$$0, 1, 3, 4full
6$$$12 \times 2$$$no additional constraints0 – 6full
Examples
Input
7 2
2 1
1 3
2 4
5 4
4 7
6 5
7
7
6
5
4
3
2
1
Output
9
4
9
9
4
9
4
Input
2 0
1 2
1
1
Output
0
Note

In the first example the responses to the queries correspond to the following sets of selected servers:

  • for server $$$1$$$ — set $$$\{1, 2, 3\}$$$ or set $$$\{1, 2, 4\}$$$;
  • for servers $$$2$$$, $$$4$$$, $$$5$$$, and $$$7$$$ — the set $$$\{2, 4, 5, 7\}$$$;
  • for server $$$3$$$ — $$$\{1, 2, 3\}$$$;
  • for server $$$6$$$ — $$$\{4, 5, 6\}$$$.