310261: CF1806E. Tree Master

E. Tree Mastertime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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

Input

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

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

ExamplesInput

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

Output

33
27

Input

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

Output

47
53
48
36
42
36
48
14

Note

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

题目大意：
给定一个带权重的树，树的节点数为n，节点编号从1到n，以节点1为根。每个节点的父节点为p_i，节点的权重为a_i。为了方便，定义p_1=0。对于树中同一深度的任意两个节点x和y，定义函数f(x,y)如下：
1. 初始化ans=0。
2. 当x和y都不为0时，执行以下操作：
- ans←ans+a_x⋅a_y；
- x←p_x；
- y←p_y。
3. f(x,y)的值为ans。

你需要处理q个查询。在第i个查询中，你会得到两个整数x_i和y_i，需要计算f(x_i,y_i)。

输入输出数据格式：
输入：
- 第一行包含两个整数n和q（2≤n≤10^5；1≤q≤10^5）。
- 第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^5）。
- 第三行包含n-1个整数p_2,…,p_n（1≤p_i - 接下来的q行，每行包含两个整数x_i和y_i（1≤x_i,y_i≤n）。保证x_i和y_i是同一深度的节点。

输出：
- q行，第i行包含一个整数，表示f(x_i,y_i)的值。

示例输入输出：
输入：
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题目大意： 给定一个带权重的树，树的节点数为n，节点编号从1到n，以节点1为根。每个节点的父节点为p_i，节点的权重为a_i。为了方便，定义p_1=0。对于树中同一深度的任意两个节点x和y，定义函数f(x,y)如下： 1. 初始化ans=0。 2. 当x和y都不为0时，执行以下操作： - ans←ans+a_x⋅a_y； - x←p_x； - y←p_y。 3. f(x,y)的值为ans。 你需要处理q个查询。在第i个查询中，你会得到两个整数x_i和y_i，需要计算f(x_i,y_i)。 输入输出数据格式： 输入： - 第一行包含两个整数n和q（2≤n≤10^5；1≤q≤10^5）。 - 第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^5）。 - 第三行包含n-1个整数p_2,…,p_n（1≤p_i