Migrated from Lutece 3136 mastree

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：根号分治

是时候成为树论大师了

给定一个 $n$ 个节点的树，每个节点都有权值 $a_i$。 对于第 $i (2\le i\le n)$ 个节点，有父亲节点 $p_i$（规定 $p_1=0$） 现有两个相同深度的节点 $x,y$，规定

$$f(x,y)=\begin{cases}0&(x=y=0)\\f(p_x,p_y)+a_x\cdot a_y&(x,y\neq0)\end{cases} $$

求 $f(x,y)$。

Input

第一行包含两个整数 $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$ 具有相同深度

Output

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

Samples

6 2
1 5 2 3 1 1
1 2 3 3 2
4 5
6 6

33
27

14 8
3 2 5 3 1 4 2 2 2 5 5 5 2 4
1 2 3 1 1 4 7 3 3 1 5 3 8
4 4
4 10
13 10
3 12
13 9
3 12
9 10
11 5

47
53
48
36
42
36
48
14

Resources

2024 UESTC ICPC Training for Data Structure