← 返回题目列表

Codeforces · 1425/I

I. 果园令人印象深刻的收获

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

Chanek 先生有一个果园,其结构为一棵有根三元树,其 $$$N$$$ 顶点编号从 $$$1$$$ 到 $$$N$$$。树的根是顶点$$$1$$$。 $$$P_i$$$ 表示顶点 $$$i$$$ 的父节点,对于 $$$(2 \le i \le N)$$$。有趣的是,树的高度不大于$$$10$$$。树的高度定义为树中从根到顶点的最大距离。

树的每个顶点都有一个灌木丛。最初,所有灌木丛都结出果实。水果不会生长在当前已经有水果的灌木丛上。顶点$$$i$$$处的灌木将在自上次收获后$$$A_i$$$天后结出果实。

Chanek 先生将参观他的果园 $$$Q$$$ 天。在 $$$i$$$ 天,他将收获顶点 $$$X_i$$$ 子树上所有有果实的灌木丛。对于每一天,确定从每个收获的灌木丛到 $$$X_i$$$ 的距离总和,以及当天收获的灌木丛的数量。收获灌木丛意味着收集灌木丛上的所有果实。

例如,如果 Chanek 先生收获了顶点 $$$X$$$ 子树上的所有水果,并收获了灌木丛 $$$[Y_1, Y_2, \dots, Y_M]$$$,则距离总和为 $$$\sum_{i = 1}^M \text{distance}(X, Y_i)$$$

树中的 $$$\text{distance}(U, V)$$$ 被定义为从 $$$U$$$ 到 $$$V$$$ 的简单路径上的边数。

输入

第一行包含两个整数 $$$N$$$ 和 $$$Q$$$ $$$(1 \le N,\ Q,\le 5 \cdot 10^4)$$$,表示顶点数和 Chanek 先生访问果园的天数。

第二行包含 $$$N$$$ 整数 $$$A_i$$$ $$$(1 \le A_i \le 5 \cdot 10^4)$$$,表示顶点 $$$i$$$ 处灌木上果实的生长速度,对于 $$$(1 \le i \le N)$$$。

第三行包含 $$$N-1$$$ 整数 $$$P_i$$$ $$$(1 \le P_i \le N, P_i \ne i)$$$,表示树中顶点 $$$i$$$ 的父节点,$$$(2 \le i \le N)$$$。保证每个顶点最多可以是 $$$3$$$ 个其他顶点的父顶点。还保证树的高度不大于$$$10$$$。

接下来的 $$$Q$$$ 行包含一个整数 $$$X_i$$$ $$$(1 \le X_i \le N)$$$,表示 Chanek 先生在 $$$i$$$ 那天的访问开始,即 $$$(1 \le i \le Q)$$$。

输出

输出 $$$Q$$$ 行,$$$i$$$ 行给出从收获的灌木丛到 $$$X_i$$$ 的距离总和,以及收获的灌木丛的数量。

示例

输入 #1

2 3
1 2
1
2
1
1

输出 #1

0 1
0 1
1 2

输入 #2

5 3
2 1 1 3 2
1 2 2 1
1
1
1

输出 #2

6 5
3 2
4 4

注意

对于第一个示例:

- 在第 1 天,Chanek 先生从顶点 $$$2$$$ 开始,可以在顶点 2 收获灌木丛。
- 第 2 天,Chanek 先生从顶点 $$$1$$$ 开始,仅从灌木丛 $$$1$$$ 收获(灌木丛 2 的果实尚未生长)。
- 第 3 天,Chanek 先生从顶点 $$$1$$$ 开始,收获灌木 $$$1$$$ 和 $$$2$$$ 上的果实。从每个收获的灌木丛到 $$$1$$$ 的距离总和为 $$$1$$$。

对于第二个示例,Chanek 先生始终从顶点 $$$1$$$ 开始。查内克先生在第一天、第二天和第三天收获的灌木丛分别为 $$$[1, 2, 3, 4, 5], [2, 3], [1, 2, 3, 5]$$$。