CF1425I.Impressive Harvesting of The Orchard

Chanek 先生有一个果园，这个果园的结构是一棵有根三叉树，共有 $N$ 个顶点，编号从 $1$ 到 $N$。树的根为顶点 $1$。对于 $2 \le i \le N$，$P_i$ 表示顶点 $i$ 的父节点。值得注意的是，这棵树的高度不超过 $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$，表示顶点数和 Chanek 先生参观果园的天数，$1 \le N, Q \le 5 \cdot 10^4$。

第二行包含 $N$ 个整数 $A_i$，表示第 $i$ 个顶点上的灌木从上次采摘后再次长出果实所需的天数，$1 \le A_i \le 5 \cdot 10^4$。

第三行包含 $N-1$ 个整数 $P_i$，表示第 $i$ 个顶点的父节点（$2 \le i \le N$），$1 \le P_i \le N, P_i \ne i$。保证每个顶点最多有 $3$ 个子节点，且树的高度不超过 $10$。

接下来 $Q$ 行，每行一个整数 $X_i$，表示第 $i$ 天 Chanek 先生从顶点 $X_i$ 开始采摘，$1 \le X_i \le N$。

输出 $Q$ 行，第 $i$ 行输出当天采摘的所有灌木到 $X_i$ 的距离之和，以及当天采摘的灌木数量。

对于第一个样例：

• 第一天，Chanek 先生从顶点 $2$ 开始，只能采摘顶点 $2$ 上的灌木。
• 第二天，Chanek 先生从顶点 $1$ 开始，只能采摘顶点 $1$ 上的灌木（顶点 $2$ 上的果实还未长出来）。
• 第三天，Chanek 先生从顶点 $1$ 开始，能采摘顶点 $1$ 和 $2$ 上的果实。所有采摘的灌木到 $1$ 的距离之和为 $1$。

对于第二个样例，Chanek 先生每天都从顶点 $1$ 开始。第一、二、三天分别采摘的灌木为 $[1, 2, 3, 4, 5]$、$[2, 3]$、$[1, 2, 3, 5]$。

由 ChatGPT 4.1 翻译