Problem Description

There are $n$ attractions on Little Bear’s map, and each attraction has a score $s_i$.

Between $n-1$ pairs of nodes, there are bidirectional direct bus routes, and each route has a cost $w_i$.

Now Little Bear is at attraction $a$, and the Commander-in-Chief is at attraction $b$. They must meet at some attraction $p$ on the path from $a$ to $b$ along a simple path, and then along a simple path go together to attraction $q$ ($q$ can be any node, and neither person will visit attraction $p$ twice).

There are $m$ queries. Given $a, b$, choose $p, q$ such that, under the condition that the total cost paid by Little Bear and the Commander-in-Chief is minimized, the total sum of attraction scores they pass through is maximized. Output this total sum of attraction scores. (That is, the sum of scores of attractions passed by Little Bear $+$ the sum of scores of attractions passed by the Commander-in-Chief.)

If an edge is traversed multiple times, its cost is counted multiple times. If an attraction is visited multiple times, its score is counted multiple times.

Input Format

The first line contains two integers $n, m$, representing the number of attractions and the number of queries.

The next line contains $n$ integers. The $i$-th integer $s_i$ represents the weight (score) of the $i$-th attraction.

The next $n-1$ lines each contain three integers $u, v, w$, indicating that there is a bidirectional bus route with cost $w$ between node $u$ and node $v$.

The next $m$ lines each contain two integers $a$ and $b$, indicating the current attractions of Little Bear and the Commander-in-Chief.

Output Format

For each query, output one integer per line representing the answer.

7 1
1 1 1 1 1 1 1
1 2 3
3 6 -4
2 5 2
1 3 6
2 4 1
3 7 5
4 7

8

10 10
786755 -687509 368192 154769 647117 -713535 337677 913223 -389809 -824004 
1 2 -785875
1 3 -77082
1 4 -973070
3 5 -97388
2 6 -112274
3 7 657757
4 8 741733
3 9 5656
4 10 -35190
3 3
3 10
7 3
5 1
2 10
10 10
1 6
7 2
8 9
9 1

971424
-1257332
1309101
3420605
-2313033
-2567048
-2467802
352646
759321
1368370

Hint

Sample Explanation

For the first sample, Little Bear’s map is shown in the figure:

Here $a=4, b=7$. Let $p=3, q=6$.

Little Bear’s path is $4\to2\to1\to3\to6$. The total cost is $1+3+6+(-4)=6$, and the total attraction score is $1+1+1+1+1=5$.

The Commander-in-Chief’s path is $7\to3\to6$. The total cost is $5+(-4)=1$, and the total attraction score is $1+1+1=3$.

The total cost paid by both is $6+1=7$, and the total attraction score passed is $5+3=8$.

It can be proven that, under the condition that the total cost is minimized, this choice maximizes the total attraction score they pass through.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $1\le n,m\le 3\times 10^5$, $\vert s_i\vert,\vert w_i\vert\le10^6$, and Little Bear’s map is a tree.

(Since Little Bear can visit attractions, why can’t bus prices and attraction scores be negative?)

Translated by ChatGPT 5