G. Два-пути
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано взвешенное дерево (неориентированный связный граф без циклов, петель и кратных ребер) из $$$n$$$ вершин. Ребро $$$\{u_j, v_j\}$$$ имеет вес $$$w_j$$$. Также, каждой вершине $$$i$$$ присвоено значение $$$a_i$$$.

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

Для каждого 2-пути $$$p$$$ можно найти его профит $$$\text{Pr}(p) = \sum\limits_{v \in \text{различные вершины в } p}{a_v} - \sum\limits_{e \in \text{различные ребра в } p}{k_e \cdot w_e}$$$, где $$$k_e$$$ равно количеству вхождений $$$e$$$ в $$$p$$$. То есть, вершины учитываются ровно один раз, а ребра — столько, сколько раз каждое встречается в $$$p$$$.

Вам необходимо ответить на $$$m$$$ запросов. Каждый запрос является парой вершин $$$(qu, qv)$$$. Для каждого запроса найдите 2-путь $$$p$$$ из $$$qu$$$ в $$$qv$$$ с максимальным профитом $$$\text{Pr}(p)$$$.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le q \le 4 \cdot 10^5$$$) — количество вершин в дереве и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — значения, присвоенные вершинам.

Следующие $$$n - 1$$$ строк содержат описания ребер: каждая строка содержит три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$, $$$1 \le w_i \le 10^9$$$) — есть ребро $$$\{u_i, v_i\}$$$ с весом $$$w_i$$$ в заданном дереве.

Следующие $$$q$$$ строк содержат запросы (по одному в строке). Каждый запрос содержит два целых числа $$$qu_i$$$ и $$$qv_i$$$ $$$(1 \le qu_i, qv_i \le n)$$$ — концы 2-пути, который Вам надо найти.

Выходные данные

Для каждого запроса выведите по одному числу в строке — максимальный профит $$$\text{Pr}(p)$$$ некоторого 2-пути $$$p$$$ с соответствующими концами.

Пример
Входные данные
7 6
6 5 5 3 2 1 2
1 2 2
2 3 2
2 4 1
4 5 1
6 4 2
7 3 25
1 1
4 4
5 6
6 4
3 4
3 7
Выходные данные
9
9
9
8
12
-14
Примечание

Разъяснение запросов:

  1. $$$(1, 1)$$$ — один из оптимальных 2-путей следующий: $$$1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$. $$$\text{Pr}(p) = (a_1 + a_2 + a_3 + a_4 + a_5) - (2 \cdot w(1,2) + 2 \cdot w(2,3) + 2 \cdot w(2,4) + 2 \cdot w(4,5)) = 21 - 2 \cdot 12 = 9$$$.
  2. $$$(4, 4)$$$: $$$4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$$$. $$$\text{Pr}(p) = (a_1 + a_2 + a_3 + a_4) - 2 \cdot (w(1,2) + w(2,3) + w(2,4)) = 19 - 2 \cdot 10 = 9$$$.
  3. $$$(5, 6)$$$: $$$5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 6$$$.
  4. $$$(6, 4)$$$: $$$6 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$$$.
  5. $$$(3, 4)$$$: $$$3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4$$$.
  6. $$$(3, 7)$$$: $$$3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 7$$$.