Description

There are $n$ data centers, numbered $1,2,\cdots,n$. They are connected by $n-1$ optical cables, forming a tree.

Each optical cable has a delay of $1$ unit time when transmitting data. The delay between two data centers is the sum of the delays of the optical cables along the path connecting them.

Now you need to choose some of these $n$ data centers as communication stations, such that the delay between any two communication stations does not exceed $d$. Let the selected communication stations be ${w_1,w_2,……,w_k}$. Then the total communication delay is the sum of delays between every pair of these $k$ communication stations.

There are $q$ queries. In each query, a data center $u$ is specified. You need to find: if $u$ must be a communication station, what is the maximum possible total communication delay.

Input Format

The first line contains two natural numbers $n,d$, representing the number of data centers and the maximum allowed delay between any two communication stations.

The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an optical cable between $u$ and $v$.

The next line contains a positive integer $q$, representing the number of queries.

The next $q$ lines each contain one positive integer $u$, representing the communication station specified in the query.

Output Format

Output $q$ lines in total. Each line contains one integer, representing the answer to that query.

6 2
1 2
2 3
1 4
4 5
4 6
6
1
2
3
4
5
6

9
4
4
9
9
9

10 2
1 2
1 3
2 4
4 5
4 6
2 7
2 8
7 9
7 10
10
1
2
3
4
5
6
7
8
9
10

16
16
4
16
9
9
16
16
9
9

Hint

For all data, $1 \leq n \leq 5\times10^5$, $0 \leq d<n$, $0 \leq q \leq 10$.

For $10\%$ of the data, $n \leq 15$.

For another $10\%$ of the data, $d=n-1$.

For another $15\%$ of the data, $n \leq 300$.

For another $15\%$ of the data, $n \leq 5000$.

For another $20\%$ of the data, $n \leq 10^5$.

For the remaining $30\%$ of the data, there are no special constraints.

Translated by ChatGPT 5