#3100. 「SNOI2019」网络

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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 行,每行一个整数表示该次询问的答案。

样例

样例输入 1

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

样例输出 1

9
4
4
9
9
9

样例输入 2

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

样例输出 2

16
16
4
16
9
9
16
16
9
9

样例 3

见附加文件。

数据范围与提示

对于所有数据, 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\% 的数据,无特殊限制。