← 返回题目列表

AtCoder · ddcc2017_final_e

E. 腿部伸展

中文机器翻译题面 查看原题

配点 : 1300 点

問題文

高桥君 N 我有一棵由顶点组成的填充树。 顶部的数字 附上 1, 2, ..., N 。

i 第一条边是顶点 a_i, b_i 相连,长度为 1 。

{\rm dist}(u, v) 到顶点 u 到顶点 定义为到 v 的最短距离。那么树的直径就是 {\rm max}_{1 ≦ u < v ≦ N}({\rm dist}(u, v)) 。

青木君看着这只毛绒动物的侧面。 1 选择一本书并检查其长度。 1 我做了几次增加它的技巧。 恶作剧的数量 已知它是 K_1, K_2, ..., K_Q 之一。

此外,由于青木更喜欢直径较短的树木,因此众所周知,他在完成所有恶作剧后对树进行了操纵,使树的直径尽可能短。

恶作剧数量 K_1, K_2, ..., K_Q 对于每种情况,找出所有恶作剧完成后树的直径。

制約

  • 3 ≦ N ≦ 200,000
  • 1 ≦ a_i, b_i ≦ N
  • 输入是一棵树 请输出
  • 1 ≦ Q ≦ 200,000
  • 0 ≦ K_1 < K_2 < ... < K_Q ≦ 10^{18}

入力

输入是按以下格式从标准输入给出的。

N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
Q
K_1 K_2 ... K_Q

出力

Q 行。 i 行显示恶作剧的数量。 请输出 K_i 时树的直径。


入力例 1

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

出力例 1

2
3
4
4
5
6
6
7
8
8

入力例 2

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

出力例 2

6
7
7
7
8
8
8
9
9
9

入力例 3

6
6 3
3 4
3 2
3 1
1 5
31
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

出力例 3

3
4
4
4
5
6
6
6
7
8
8
8
9
10
10
10
11
12
12
12
13
14
14
14
15
16
16
16
17
18
18