D. Сумма на пути

В вершинах дерева записаны числа. Для каждого запроса $(u, v)$ найдите сумму чисел во всех вершинах пути из $u$ в $v$, включая концы.

В первой строке $n$ ($1 \le n \le 2 \cdot 10^5$). Во второй строке $n$ целых чисел $v_i$ ($|v_i| < 10^9$) — значения в вершинах, пронумерованных от $1$ до $n$.

В следующих $n-1$ строках рёбра дерева: два номера вершин.

Далее число $m$ ($1 \le m \le 2 \cdot 10^5$) и $m$ строк с запросами $(x_i, y_i)$.

Для каждого запроса выведите сумму значений на пути.