← 返回题目列表

Codeforces · 1000/G

G. 两条路径

中文机器翻译题面 查看原题

给您一棵带有 $$$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$$$。