E. Мастер деревьев
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево с $$$n$$$ взвешенными вершинами, пронумерованными от $$$1$$$ до $$$n$$$. Корнем дерева является $$$1$$$. Родитель вершины $$$i$$$ — вершина $$$p_i$$$, а вес вершины $$$i$$$ — число $$$a_i$$$. Для удобства определим $$$p_1=0$$$.

Для двух вершин $$$x$$$ и $$$y$$$ одинаковой глубины$$$^\dagger$$$, определим $$$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)$$$.

Примеры
Входные данные
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
Примечание

Рассмотрим первый пример.

В первом запросе ответ – $$$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$$$.