Вам дано дерево с \(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\).
Выходные данные
Выведите \(q\) строк, \(i\)-я строка содержит одно целое число — значение \(f(x_i,y_i)\).
Примечание
Рассмотрим первый пример.
В первом запросе ответ – \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
1 5 2 3 1 1
1 2 3 3 2
4 5
6 6
|
33
27
|
|
2
|
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
|