E - 足のばし 解説 /

実行時間制限: 4 sec / メモリ制限: 512 MB

配点 : 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