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 翻译