CF1000G.Two-Paths

You are given a weighted tree (undirected connected graph with no cycles, loops or multiple edges) with $n$ vertices. The edge ${u_j, v_j}$ has weight $w_j$. Also each vertex $i$ has its own value $a_i$ assigned to it.

Let's call a path starting in vertex $u$ and ending in vertex $v$, where each edge can appear no more than twice (regardless of direction), a 2-path. Vertices can appear in the 2-path multiple times (even start and end vertices).

For some 2-path $p$ profit $\text{Pr}(p) = \sum\limits_{v \in \text{distinct vertices in } p}{a_v} - \sum\limits_{e \in \text{distinct edges in } p}{k_e \cdot w_e}$, where $k_e$ is the number of times edge $e$ appears in $p$. That is, vertices are counted once, but edges are counted the number of times they appear in $p$.

You are about to answer $m$ queries. Each query is a pair of vertices $(qu, qv)$. For each query find 2-path $p$ from $qu$ to $qv$ with maximal profit $\text{Pr}(p)$.

给你一棵带权树（即无环、无自环、无重边的无向连通图），该树包含 $n$ 个顶点。边 $\{u_j, v_j\}$ 的权重为 $w_j$。此外，每个顶点 $i$ 都被赋予一个值 $a_i$。

我们称一条从顶点 $u$ 出发、到顶点 $v$ 结束的路径为2-路径（2-path），其中每条边在该路径中至多出现两次（不区分方向）。顶点在 2-路径中可以多次出现（包括起点和终点）。

对于某条 2-路径 $p$，其收益（profit）定义为

$$\text{Pr}(p) = \sum\limits_{v \in \text{distinct vertices in } p}{a_v} - \sum\limits_{e \in \text{distinct edges in } p}{k_e \cdot w_e},$$

其中 $k_e$ 表示边 $e$ 在 $p$ 中出现的次数。即：顶点仅按其是否在 $p$ 中出现过计一次，而边则按其在 $p$ 中实际出现的次数加权计入。

你将回答 $m$ 个查询。每个查询给出一对顶点 $(qu, qv)$。对每个查询，请找出一条从 $qu$ 到 $qv$ 的 2-路径 $p$，使得其收益 $\text{Pr}(p)$ 最大。

The first line contains two integers $n$ and $q$ ($2 \le n \le 3 \cdot 10^5$, $1 \le q \le 4 \cdot 10^5$) — the number of vertices in the tree and the number of queries.

The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$ — the values of the vertices.

Next $n - 1$ lines contain descriptions of edges: each line contains three space separated integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le w_i \le 10^9$) — there is edge ${u_i, v_i}$ with weight $w_i$ in the tree.

Next $q$ lines contain queries (one per line). Each query contains two integers $qu_i$ and $qv_i$ $(1 \le qu_i, qv_i \le n)$ — endpoints of the 2-path you need to find.

第一行包含两个整数 $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-路径”的两个端点。

For each query print one integer per line — maximal profit $\text{Pr}(p)$ of the some 2-path $p$ with the corresponding endpoints.

对于每个查询，每行输出一个整数——具有对应端点的某条 2-路径 $p$ 的最大收益 $\text{Pr}(p)$。

Explanation of queries:

1. $(1, 1)$ — one of the optimal 2-paths is the following: $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$.

查询解释：

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$。