首先可以用一次 DFS 算出每个点的深度 $dep$ 和初始的代价 $cost$。

不妨把询问点按 $cost$ 从小到大排序为 $v_1,\ldots,v_k$。那么假设不加任何点，答案就是 $cost(v_k)$。

要让答案变小，必须让 $v_k$ 的代价变小，所以加的点必须是 $v_k$ 的祖先，且深度尽可能大。同理，如果我们要让答案小于 $cost(v_i)$，那么必须让 $v_i,\ldots,v_k$ 的代价都变小，加的点也就必须是 $v_i,\ldots,v_k$ 的公共祖先，且深度尽可能大，也就是它们的 LCA。因此我们可以用 $\max\{cost(v_{i-1}),\max\{dep(v_i),\ldots,dep(v_k)\}-dep(lca(v_i,\ldots,v_k))\}$ 来更新答案。这里计算的代价可能比实际的代价要大，但如果出现这样的情况，说明某个 $v_j(i\le j\le k)$ 的代价还是 $cost(v_j)$，也就无法更新答案。

时间复杂度 $O(n+\sum_{i=1}^qk_i\log n)$。