题目描述

有 $n$ 个数据中心，编号为 $1,2,\dots ,n$。它们被 $n-1$ 条光缆连通，形成一棵树。

每条光缆传输数据时有 $1$ 单位时间的延迟，两个数据中心之间的延迟为连接它们的光缆的延迟之和。

现在要在这 $n$ 个数据中心中选若干个作为通讯站，要求任意两个通讯站之间的延迟不超过 $d$。设选出的通讯站为 $\{w_1,w_2,\dots,w_k\}$，则通讯总延迟为这 $k$ 个通讯站两两之间的延迟之和。

现在有 $q$ 次询问，每次选定一个数据中心 $u$，你需要求出：如果 $u$ 是一个通讯站，最大可能的通讯总延迟是多少。

输入格式

第一行两个自然数 $n, d$，分别表示数据中心的个数和两个通讯站之间最大允许的延迟。

接下来 $n-1$ 行每行两个正整数 $u,v$ 表示 $u$ 和 $v​$ 之间有一条光缆。

接下来一行一个正整数 $q​$ 表示询问次数。

接下来 $q$ 行每行一个正整数 $u​$ 表示询问中选定的通讯站。

输出格式

输出共 $q$ 行，每行一个整数表示该次询问的答案。

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

数据范围与提示

对于所有数据，$1\le n\le 5\times 10^5,0\le d< n,0\le q\le 10$。

• 对于 $10\%$ 的数据，$n\le 15$；
• 对于另外 $10\%$ 的数据，$d=n-1$；
• 对于另外 $15\%$ 的数据，$n\le 300$；
• 对于另外 $15\%$ 的数据，$n \le 5000$；
• 对于另外 $20\%$ 的数据，$n \le 10^5$；
• 对于余下 $30\%$ 的数据，无特殊限制。