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