CF1806E Tree Master

给定一棵有 $n$ 个带权顶点的树，顶点编号为 $1$ 到 $n$，以顶点 $1$ 为根。顶点 $i$ 的父节点为 $p_i$，顶点 $i$ 的权值为 $a_i$。为方便起见，定义 $p_1=0$。 对于两个深度相同的顶点 $x$ 和 $y$，定义 $f(x, y)$ 如下： - 初始化 $\mathrm{ans}=0$。 - 当 $x$ 和 $y$ 都不为 $0$ 时，重复以下操作： - $\mathrm{ans} \leftarrow \mathrm{ans} + a_x \cdot a_y$； - $x \leftarrow p_x$； - $y \leftarrow p_y$。 - $f(x, y)$ 的值即为最终的 $\mathrm{ans}$。 你需要处理 $q$ 个询问。对于第 $i$ 个询问，给定两个整数 $x_i$ 和 $y_i$，你需要计算 $f(x_i, y_i)$。 $^\dagger$ 顶点 $v$ 的深度定义为从树根到顶点 $v$ 的唯一路径上的边数。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 10^5$，$1 \le q \le 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^5$）。 第三行包含 $n-1$ 个整数 $p_2, \ldots, p_n$（$1 \le p_i < i$）。 接下来的 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$）。保证 $x_i$ 和 $y_i$ 的深度相同。

输出 $q$ 行，第 $i$ 行输出 $f(x_i, y_i)$ 的值。

考虑第一个样例： 在第一个询问中，答案为 $a_4 \cdot a_5 + a_3 \cdot a_3 + a_2 \cdot a_2 + a_1 \cdot a_1 = 3 + 4 + 25 + 1 = 33$。 在第二个询问中，答案为 $a_6 \cdot a_6 + a_2 \cdot a_2 + a_1 \cdot a_1 = 1 + 25 + 1 = 27$。 由 ChatGPT 4.1 翻译