#P1806E. Tree Master
-
ID: 8621
Type: RemoteJudge
3000ms
1024MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Tree Master
Description
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)$.
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)$.
6 2
1 5 2 3 1 1
1 2 3 3 2
4 5
6 6
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
33
27
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$.