树上点积

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定一棵有 $n$ 个带权顶点的树，顶点编号为 $1$ 到 $n$，以顶点 $1$ 为根。顶点 $i$ 的父节点为 $p_i$，顶点 $i$ 的权值为 $a_i$。定义 $p_1=0$。

对于两个深度相同的顶点 $x,y$，定义

$$f(x,y)=a_xa_y+a_{p_x}a_{p_y}+a_{p_{p_x}}a_{p_{p_y}}+\cdots,$$

直到两个点同时越过根节点为止。

你需要回答 $q$ 个询问。每个询问给出两个深度相同的顶点 $x,y$，求 $f(x,y)$。

输入格式

第一行包含两个整数 $n,q$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行包含 $n-1$ 个整数 $p_2,p_3,\ldots,p_n$。

接下来 $q$ 行，每行包含两个整数 $x,y$。保证 $x,y$ 深度相同。

输出格式

输出 $q$ 行，每行一个整数，表示对应询问的答案。

样例输入 1

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

样例输出 1

33
27

样例输入 2

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

样例输出 2

47
53
48
36
42
36
48
14

数据范围

对于所有数据：$2\le n\le 10^5$，$1\le q\le 10^5$，$1\le a_i\le 10^5$，$1\le p_i<i$。

子任务编号	分值	特殊限制
1	20	对所有 $2\le i\le n$，均有 $p_i=i-1$
2	40	$n,q\le 2000$
3		无特殊限制