AT_tenka1_2015_final_f 根付き木のみさわさん

高桥君家的院子里，长着一棵以顶点 $1$ 为根的有根树，这棵树被称为“みさわさん”。 在第 $i$ 天早晨，“みさわさん”会在 $M_i$ 个顶点 $v_{i,1},\ldots,v_{i,M_i}$ 上结出果实。 然而，在同一天的晚上，会有鸟飞来，把剩下的所有果实都吃掉。 高桥君每天可以选择“みさわさん”的一个顶点进行摇晃。 如果摇晃顶点 $w$，那么他可以获得 $w$ 的所有子孙（包括 $w$ 本身）上结的所有果实。 高桥君希望在第 $i$ 天能从“みさわさん”上获得至少 $K_i$ 个果实。 请你帮高桥君找出，通过摇晃可以获得至少 $K_i$ 个果实的顶点中，距离根最远的那个顶点，并输出该顶点到根的距离。 这里，任一顶点到根的距离，指的是从根到该顶点的唯一简单路径上包含的边的数量。

输入按以下格式从标准输入读入。 > $N$ $a_1$ $b_1$ $a_2$ $b_2$ : $a_{N-1}$ $b_{N-1}$ $Q$ $M_1$ $K_1$ $v_{1,1}$ $v_{1,2}$ ... $v_{1,M_1}$ : $M_Q$ $K_Q$ $v_{Q,1}$ $v_{Q,2}$ ... $v_{Q,M_Q}$ - 第 $1$ 行，给出“みさわさん”的顶点数 $N$，$3 \leq N \leq 10^5$。 - 接下来的 $N-1$ 行，第 $i$ 行给出一条边连接的两个顶点 $a_i, b_i$，$1 \leq a_i < b_i \leq N$，用空格分隔。 - 保证“みさわさん”是一棵树。 - 第 $N+1$ 行，给出高桥君采摘果实的天数 $Q$，$1 \leq Q \leq 10^5$。 - 接下来的 $2Q$ 行中， - 第 $2i-1$ 行给出第 $i$ 天“みさわさん”结的果实数 $M_i$ 和高桥君希望采摘的果实数 $K_i$，$1 \leq K_i \leq M_i \leq N$。 - 第 $2i$ 行给出第 $i$ 天“みさわさん”结有果实的 $M_i$ 个顶点编号。 - 输入保证 $\sum M_i \leq 10^5$。

对于每一天的输入，输出满足条件的顶点中，距离根最远的顶点到根的距离，每行输出一个答案。输出末尾需换行。

## 部分分 本题设有部分分。 - 对于 $1 \leq N \leq 100$ 的数据集，答对可得 $20$ 分。 - 对于所有数据集全部答对可再得 $110$ 分，总分为 $130$ 分。 ## 样例解释 1 - 第 $1$ 个查询，“みさわさん”在顶点 $4,5$ 上结了 $2$ 个果实。在能获得 $2$ 个果实的顶点中，距离根最远的是顶点 $3$，其到根的距离为 $2$。 - 第 $2$ 个查询，“みさわさん”在顶点 $1$ 上结了 $1$ 个果实。在能获得 $1$ 个果实的顶点中，距离根最远的是顶点 $1$，其到根的距离为 $0$。 - 第 $3$ 个查询，“みさわさん”在顶点 $2,1$ 上结了 $2$ 个果实。在能获得 $1$ 个果实的顶点中，距离根最远的是顶点 $2$，其到根的距离为 $1$。 由 ChatGPT 4.1 翻译