给您一棵树,其中 $$$n$$$ 加权顶点标记为从 $$$1$$$ 到 $$$n$$$,根于顶点 $$$1$$$。顶点$$$i$$$的父节点是$$$p_i$$$,顶点$$$i$$$的权重是$$$a_i$$$。为了方便起见,定义$$$p_1=0$$$。
对于深度相同$$$^\dagger$$$的两个顶点$$$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)$$$的值。
示例
输入 #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
注意
考虑第一个例子:
在第一个查询中,答案是 $$$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$$$。