CF2033G.Sakurako and Chefir

给定一棵有 $n$ 个顶点的树，根节点为 $1$。Sakurako 在带着她的猫 Chefir 散步时分心了，Chefir 跑丢了。

为了帮助 Sakurako，Kosuke 记录了他的 $q$ 次猜测。在第 $i$ 次猜测中，他假设 Chefir 在顶点 $v_i$ 处迷路，并且有 $k_i$ 点体力。

此外，对于每一次猜测，Kosuke 假设 Chefir 可以沿着树的边任意次移动：

• 如果从顶点 $a$ 移动到顶点 $b$，且 $a$ 是 $b$ 的祖先，则体力不会减少；
• 如果从顶点 $a$ 移动到顶点 $b$，且 $a$ 不是 $b$ 的祖先，则 Chefir 的体力减少 $1$。

如果 Chefir 的体力为 $0$，则不能进行第二种类型的移动。

对于每一次猜测，你需要求出 Chefir 从顶点 $v_i$ 出发、拥有 $k_i$ 点体力时，能够到达的最远顶点的距离。

$^*$ 如果从 $b$ 到根节点的最短路径经过 $a$，则称 $a$ 是 $b$ 的祖先。

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。

每个测试用例描述如下：

• 第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树的顶点数。
• 接下来的 $n-1$ 行，每行描述一条树的边。保证这些边构成一棵树。
• 下一行包含一个整数 $q$（$1\le q\le 2 \cdot 10^5$），表示 Kosuke 的猜测次数。
• 接下来的 $q$ 行，每行包含两个整数 $v_i$、$k_i$（$1\le v_i \le n, 0 \le k_i\le n$）。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $2\cdot 10^5$。

对于每个测试用例的每一次猜测，输出 Chefir 能够到达的最远顶点的距离。

在第一个样例中：

• 对于第一个询问，可以从顶点 $5$ 走到顶点 $3$（此时体力减少 $1$ 变为 $0$），然后可以走到顶点 $4$；
• 对于第二个询问，从顶点 $3$ 出发，体力为 $1$，只能到达顶点 $2$、$3$、$4$ 和 $5$；
• 对于第三个询问，从顶点 $2$ 出发，体力为 $0$，只能到达顶点 $2$、$3$、$4$ 和 $5$。

由 ChatGPT 4.1 翻译