Вам задано взвешенное дерево (неориентированный связный граф без циклов, петель и кратных ребер) из \(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)\).
Выходные данные
Для каждого запроса выведите по одному числу в строке — максимальный профит \(\text{Pr}(p)\) некоторого 2-пути \(p\) с соответствующими концами.
Примечание
Разъяснение запросов:
- \((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\).
- \((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\).
- \((5, 6)\): \(5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 6\).
- \((6, 4)\): \(6 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4\).
- \((3, 4)\): \(3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4\).
- \((3, 7)\): \(3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|