CF1806E.Tree Master

You are given a tree with $n$ weighted vertices labeled from $1$ to $n$ rooted at vertex $1$. The parent of vertex $i$ is $p_i$ and the weight of vertex $i$ is $a_i$. For convenience, define $p_1=0$.

For two vertices $x$ and $y$ of the same depth$^\dagger$, define $f(x,y)$ as follows:

• Initialize $\mathrm{ans}=0$.
• While both $x$ and $y$ are not $0$:
  • $\mathrm{ans}\leftarrow \mathrm{ans}+a_x\cdot a_y$;
  • $x\leftarrow p_x$;
  • $y\leftarrow p_y$.
• $f(x,y)$ is the value of $\mathrm{ans}$.

You will process $q$ queries. In the $i$-th query, you are given two integers $x_i$ and $y_i$ and you need to calculate $f(x_i,y_i)$.

$^\dagger$ The depth of vertex $v$ is the number of edges on the unique simple path from the root of the tree to vertex $v$.

你被给定一棵包含 $n$ 个带权顶点的树，顶点编号为 $1$ 到 $n$，根节点为顶点 $1$。顶点 $i$ 的父节点为 $p_i$，其权值为 $a_i$。为方便起见，定义 $p_1 = 0$。

对于两个深度相同$^\dagger$ 的顶点 $x$ 和 $y$，定义函数 $f(x,y)$ 如下：

• 初始化 $\mathrm{ans} = 0$；
• 当 $x \neq 0$ 且 $y \neq 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$ 的唯一简单路径上的边数。

The first line contains two integers $n$ and $q$ ($2 \le n \le 10^5$; $1 \le q \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$).

The third line contains $n-1$ integers $p_2, \ldots, p_n$ ($1 \le p_i \lt i$).

Each of the next $q$ lines contains two integers $x_i$ and $y_i$ ($1\le x_i,y_i\le n$). It is guaranteed that $x_i$ and $y_i$ are of the same depth.

第一行包含两个整数 $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 \lt i$）。

接下来的 $q$ 行中，每行包含两个整数 $x_i$ 和 $y_i$（$1\le x_i,y_i\le n$）。保证 $x_i$ 和 $y_i$ 处于同一深度。

Output $q$ lines, the $i$-th line contains a single integer, the value of $f(x_i,y_i)$.

输出 $q$ 行，第 $i$ 行包含一个整数，即 $f(x_i,y_i)$ 的值。

Consider the first example:

In the first query, the answer is $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$.

In the second query, the answer is $a_6\cdot a_6+a_2\cdot a_2+a_1\cdot a_1=1+25+1=27$.

考虑第一个例子：

在第一个查询中，答案为 $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$。