给您一棵带有 $$$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)$$$。对于每个查询,找到从 $$$qu$$$ 到 $$$qv$$$ 的 2 条路径 $$$p$$$,利润最大 $$$\text{Pr}(p)$$$。
输入
第一行包含两个整数 $$$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$$$) — 树中存在权重为 $$$w_i$$$ 的边 $$$\{u_i, v_i\}$$$。
接下来的 $$$q$$$ 行包含查询(每行一个)。每个查询包含两个整数 $$$qu_i$$$ 和 $$$qv_i$$$ $$$(1 \le qu_i, qv_i \le n)$$$ — 您需要查找的 2 条路径的端点。
输出
对于每个查询,每行打印一个整数 - 某些 2 路径 $$$p$$$ 与相应端点的最大利润 $$$\text{Pr}(p)$$$ 。
示例
输入 #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
输出 #1
9 9 9 8 12 -14
注意
查询说明:
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$$$。