E. Tree Master
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\).
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)\).
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\).