题目背景

原题链接：https://oier.team/problems/S7B。

题目描述

M 国有 $n$ 个城市和 $n - 1$ 条双向道路，城市编号为 $1,2,\dots,n$，保证这些城市连通，即构成了一棵树。其中，第 $i$ 条道路连接了城市 $u_i$ 和城市 $v_i$，路费为 $w_i$。你是一名演说家，每天都要在 M 国举办三场演讲，每场演讲都会在某一个城市进行。在城市 $i$ 举办一场演讲可以获得 $c_i$ 的收入，同一天内可以在同一个城市举办多场演讲。

接下来有 $q$ 天，第 $i$ 天的安排如下：你的第一场演讲必须在城市 $x_i$ 举行，第三场演讲必须在城市 $y_i$ 举行，而第二场演讲所在的城市可以自由选择。设第二场演讲所在的城市为 $z_i$，你需要向交通管理局支付经过 $x_i \to z_i$ 路径以及 $z_i \to y_i$ 路径上所有道路的路费。注意，一条道路如果被多次经过，每次经过都需要支付相应的路费。

对于每一天，请计算当天可以获得的最大利润，即总收入减去总路费的最大值。注意，答案可能是负数。

输入格式

第一行，两个正整数 $n,q$。

第二行，$n$ 个非负整数 $c_1,c_2,\dots,c_n$。

接下来 $n - 1$ 行，每行三个非负整数 $u_i,v_i,w_i$，表示第 $i$ 条道路。

接下来 $q$ 行，每行两个正整数 $x_i,y_i$，表示第 $i$ 天的安排。

输出格式

$q$ 行，每行一个整数，表示第 $i$ 天的最大利润。

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

12
10
6

提示

【样例解释 #1】

• 第一天选择城市 $1$，答案为 $4 + 4 + 4 - 0 - 0 = 12$。
• 第二天选择城市 $4$，答案为 $2 + 7 + 7 - 6 - 0 = 10$。
• 第三天选择城市 $2$，答案为 $2 + 6 + 2 - 2 - 2 = 6$。

【样例 #2】

见附件中的 speaker/speaker2.in 与 speaker/speaker2.ans。

该组样例满足测试点 $7\sim 8$ 的约束条件。

【样例 #3】

见附件中的 speaker/speaker3.in 与 speaker/speaker3.ans。

该组样例满足测试点 $11\sim 13$ 的约束条件。

【样例 #4】

见附件中的 speaker/speaker4.in 与 speaker/speaker4.ans。

该组样例满足测试点 $17\sim 19$ 的约束条件。

【数据范围】

对于所有测试数据，保证：$1\le n, q\le 2\times 10^5$，$1\le u_i, v_i \le n$，$0\le w_i, c_i\le 10^9$，所有城市和道路构成了一棵树，$1\le x_i, y_i \le n$。

测试点编号	$n\le$	$q\le$	特殊性质
$1\sim 4$	$400$		无
$5$	$2000$	$2000$	A
$6$			B
$7\sim 8$			无
$9$		$2\times 10^5$	A
$10$			C
$11\sim 13$			无
$14\sim 15$	$2\times 10^5$	$3$
$16$		$2\times 10^5$	A
$17\sim 19$			C
$20\sim 25$			无

• 特殊性质 A：每个城市至多被两条道路连接。
• 特殊性质 B：存在一座城市 $i$（$1\le i\le n$），满足对于所有其他城市 $j$（$1\le j\le n$、$j \ne i$），都存在连接城市 $i$ 与城市 $j$ 的道路。
• 特殊性质 C：对所有 $1 \le i \le q$，都有 $x_i = 1$。