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$ .

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 < 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.

Output $q$ lines, the $i$ -th line contains a single integer, the value of $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$ .