CF1000G Two-Paths

给定一棵带权树（无向连通无环图，无自环，无重边），共有 $n$ 个顶点。第 $j$ 条边 $\{u_j, v_j\}$ 的权值为 $w_j$。每个顶点 $i$ 有一个权值 $a_i$。 我们定义一条从顶点 $u$ 到顶点 $v$ 的路径为“2-路径”，如果每条边在路径中出现次数不超过两次（无论方向如何）。顶点在 2-路径中可以多次出现（起点和终点也可以多次出现）。 对于某条 2-路径 $p$，其收益定义为 $$ \text{Pr}(p) = \sum\limits_{v \in \text{路径中所有不同顶点}}{a_v} - \sum\limits_{e \in \text{路径中所有不同边}}{k_e \cdot w_e} $$ 其中 $k_e$ 表示边 $e$ 在路径 $p$ 中出现的次数。也就是说，顶点的权值只计算一次，但边的权值按出现次数累加。 你需要回答 $m$ 个询问。每个询问给出一对顶点 $(qu, qv)$。对于每个询问，求从 $qu$ 到 $qv$ 的所有 2-路径中，收益 $\text{Pr}(p)$ 最大的那一条。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 3 \times 10^5$，$1 \le q \le 4 \times 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$），表示树中存在一条权值为 $w_i$ 的边 $\{u_i, v_i\}$。 接下来 $q$ 行，每行包含两个整数 $qu_i, qv_i$（$1 \le qu_i, qv_i \le n$），表示一次询问，需要你找出以这两个顶点为端点的最大收益 2-路径。

对于每个询问，输出一行一个整数，表示对应端点的最大收益 2-路径的收益 $\text{Pr}(p)$。

关于样例询问的解释： 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$。 由 ChatGPT 4.1 翻译