AT_ddcc2017_final_e 足のばし

高橋君有一个由 $N$ 个顶点组成的树状毛绒玩具。顶点编号为 $1, 2, ..., N$。 第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，长度为 $1$。 我们定义 ${\rm dist}(u, v)$ 为顶点 $u$ 到顶点 $v$ 的最短距离。那么，这棵树的直径为 ${\rm max}_{1 \leq u < v \leq N}({\rm dist}(u, v))$。 青木君对这只毛绒玩具做了一些恶作剧，每次选择一条边，并将其长度增加 $1$。已知恶作剧的次数可能为 $K_1, K_2, ..., K_Q$ 其中之一。 另外，青木君更喜欢直径较小的树，所以他总是让最终树的直径尽可能小。 请分别对于每一个恶作剧次数 $K_1, K_2, ..., K_Q$，输出所有恶作剧结束后树的直径。

输入以以下格式从标准输入读入。 > $N$ > $a_1$ $b_1$ > $a_2$ $b_2$ > $\vdots$ > $a_{N-1}$ $b_{N-1}$ > $Q$ > $K_1$ $K_2$ $\cdots$ $K_Q$

输出 $Q$ 行。第 $i$ 行输出当恶作剧次数为 $K_i$ 时，树的最终直径。

### 限制条件 - $3 \leq N \leq 200,\!000$ - $1 \leq a_i, b_i \leq N$ - 输入数据保证构成一棵树 - $1 \leq Q \leq 200,\!000$ - $0 \leq K_1 < K_2 < \cdots < K_Q \leq 10^{18}$ 由 ChatGPT 5 翻译