← 返回题目列表

Codeforces · 2033/G

G. 樱子和Chefir

中文机器翻译题面 查看原题

给定一棵树,其中 $$$n$$$ 个顶点以顶点 $$$1$$$ 为根。当樱子带着她的猫谢菲尔走过它时,她分心了,谢菲尔逃跑了。

为了帮助樱子,小介记录了他的 $$$q$$$ 猜测。在第 $$$i$$$ 次猜测中,他假设 Chefir 在顶点 $$$v_i$$$ 处迷路并且拥有 $$$k_i$$$ 耐力。

此外,对于每个猜测,Kosuke 都假设 Chefir 可以沿着边缘移动任意次数:

- 从顶点$$$a$$$到顶点$$$b$$$,如果$$$a$$$是$$$b$$$的祖先$$$^{\text{∗}}$$$,则耐力不会改变;
- 从顶点$$$a$$$到顶点$$$b$$$,如果$$$a$$$不是$$$b$$$的祖先,那么Chefir的耐力会减少$$$1$$$。

如果Chefir的耐力为$$$0$$$,他就无法进行第二种类型的动作。

对于每个假设,您的任务是找到 Chefir 从顶点 $$$v_i$$$ 到具有 $$$k_i$$$ 耐力的最远顶点的距离。

输入

第一行包含一个整数 $$$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$$$ 行描述了 Kosuke 的猜测,其中有两个整数 $$$v_i$$$, $$$k_i$$$ $$$(1\le v_i \le n, 0 \le k_i\le n)$$$。

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

输出

对于每个测试用例和每个猜测,输出 Chefir 从具有 $$$k_i$$$ 耐力的起点 $$$v_i$$$ 可以到达的最远顶点的最大距离。

示例

输入 #1

3
5
1 2
2 3
3 4
3 5
3
5 1
3 1
2 0
9
8 1
1 7
1 4
7 3
4 9
3 2
1 5
3 6
7
6 0
2 3
6 2
8 2
2 4
9 2
6 3
6
2 1
2 5
2 4
5 6
4 3
3
3 1
1 3
6 5

输出 #1

2 1 2 
0 5 2 4 5 5 5 
1 3 4

注意

在第一个示例中:

- 在第一个查询中,你可以从顶点$$$5$$$到顶点$$$3$$$(之后你的体力会减少$$$1$$$,变成$$$0$$$),然后你可以到顶点$$$4$$$;
- 在第二个查询中,从具有 $$$1$$$ 耐力的顶点 $$$3$$$ 开始,您只能到达顶点 $$$2$$$、$$$3$$$、$$$4$$$ 和 $$$5$$$;
- 在第三个查询中,从具有 $$$0$$$ 耐力的顶点 $$$2$$$ 开始,您只能到达顶点 $$$2$$$、$$$3$$$、$$$4$$$ 和 $$$5$$$;