← 返回题目列表

Codeforces · 2223/C

C. Zhily和路标

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

返回基地时,吉莉迷路了。他发现前面的路形成了一棵树。每一个岔路口,都有一个路标,但这些路标受到异常磁场的影响,不断旋转。芝莉开始担心吉莉,想问你几个问题。每次,在给定的特定时刻,他都会询问如果从头开始,吉莉最终会停在哪个节点。

给你一棵有$$$n$$$节点的树,根在$$$1$$$。节点 $$$u$$$ 有 $$$d_u$$$ 子节点,按节点索引升序排序,即 $$$s_{u,0},\ldots,s_{u,d_u-1}$$$。跨越每条边都需要一些时间;具体来说,穿过节点 $$$u$$$ 与其父节点之间的边所需的时间是 $$$l_u$$$。

树中的每个非叶节点都有一个指向其子节点之一的路标。当你处于这样一个节点时,你必须立即移动到它指向的子节点,以这种方式继续,直到到达叶节点,并立即停止。

路标随着时间的推移而变化。在时间 $$$m$$$ 处,节点 $$$u$$$ 的路标指向其第 $$$(m\bmod d_u+1)$$$ 个子节点,即节点 $$$s_{u,m \bmod d_u}$$$。

现在有 $$$q$$$ 查询。在每个查询中,您都会得到$$$m$$$,并且您需要确定如果您在时间$$$m$$$从根开始,最终将到达的叶节点的索引。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个正整数 $$$n,q$$$ ($$$1 \le n \le 5 \cdot 10^5,1 \le q \le 10^6$$$)。

第二行包含 $$$n-1$$$ 正整数 $$$f_2,\ldots,f_n$$$ ($$$1 \le f_u \lt u$$$),其中 $$$f_u$$$ 表示节点 $$$u$$$ 的父节点的索引。

第三行包含 $$$n-1$$$ 非负整数 $$$l_2,\ldots,l_n$$$ ($$$0 \le l_u \le 10^9$$$),其中 $$$l_u$$$ 表示穿过节点 $$$u$$$ 与其父节点之间的边所需的时间。

第四行包含 $$$q$$$ 非负整数 $$$m_1,\ldots,m_{q}$$$ ($$$0 \le m_i \le 10^{18}$$$),表示 $$$q$$$ 查询。

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

保证所有测试用例的 $$$q$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出一行包含 $$$q$$$ 正整数,代表每个查询的答案。

示例

输入
复制

2
3 1
1 1
10 20
4
10 5
1 2 2 2 1 1 3 4 5
1 2 3 4 5 6 7 8 9
1 2 3 4 5

输出
复制

2
6 7 9 6 7

注意

第一个测试用例中的树如下所示。

如果您在时间 $$$4$$$ 开始,那么此时节点 $$$1$$$ 的路标指向节点 $$$2$$$。您将在时间 $$$14$$$ 到达节点 $$$2$$$ 并在那里停留。

第二个测试用例中的树如下所示。

如果您在时间 $$$3$$$ 开始,那么此时节点 $$$1$$$ 的路标指向节点 $$$2$$$。您将在时间 $$$4$$$ 到达节点 $$$2$$$。此时,节点$$$2$$$的路标指向节点$$$4$$$,因此你将在$$$7$$$时刻到达节点$$$4$$$。此时,节点 $$$4$$$ 的路标指向节点 $$$9$$$,因此您将在 $$$15$$$ 时刻到达节点 $$$9$$$ 并停在那里。