Tree Master
Contest: Codeforces Round 858 (Div. 2)
Difficulty rating: 2200
Tags: brute force, data structures, dfs and similar, trees

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 format:
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 format:
Output $$$q$$$ lines, the $$$i$$$-th line contains a single integer, the value of $$$f(x_i,y_i)$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

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

Example input:
6 2
1 5 2 3 1 1
1 2 3 3 2
4 5
6 6

Example output:
33
27

Example 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

Example output:
47
53
48
36
42
36
48
14

Editorial:
Hint 1: The time complexity of the solution is $$$O(n\sqrt{n})$$$.
Hint 2: Brute force with something to store the answer.
The solution turns out quite easy: just store the answer to each pair of $$$(x,y)$$$ when computing the answer by climbing up on the tree. If we see the time complexity of hash table as $$$O(1)$$$, then the time complexity and memory complexity are both $$$O(n\sqrt{n})$$$. Let's prove it.
We will see $$$n=q$$$ in the following proof. It is clear that the above solution's time complexity depends on the number of different pairs $$$(x,y)$$$ which we encounter when climbing. Assume the $$$i$$$-th depth of the tree has $$$s_i$$$ nodes, then its contribution to things above is $$$\min(s_i^2,n)$$$. It's easy to discover that when $$$s_i>\sqrt{n}$$$, the contribution of it will equal to the contribution when $$$s_i=\sqrt{n}$$$. So, making all $$$s_i$$$ not greater than $$$\sqrt{n}$$$ will contribute more. Therefore, the time complexity is $$$O(\sum_{i=1}^k s_i^2)$$$. When $$$s_i=\sqrt{n}$$$, the formula above has a maximum value of $$$n\sqrt{n}$$$, because $$$(a+b)^2\ge a^2+b^2$$$.
In fact, we don't need to use hash table in this problem. If there exists a pair of $$$(x,y)$$$ of depth $$$i$$$ such that $$$s_i> \sqrt{n}$$$, then we don't need to store $$$(x,y)$$$. Since the amount of $$$i$$$ such that $$$s_i>\sqrt{n}$$$ are not greater than $$$\sqrt{n}$$$, the time complexity won't change. For other pairs of $$$(x,y)$$$ we can simply store them in an array, then the memory complexity won't change.