Two-Paths

题意翻译

给你一棵 $n$ 个节点的树，每条边有权值 $w$ ,每个点有权值 $a$ ，权值范围都是 $[1,10^9]$ 。 定义2-Path为每条边最多经过两次的路径，路径权值为 $\sum a_v-\sum w_e k_e$ , $k_e$ 表示每条边的经过次数。 有 $Q$ 个询问，每次询问从 $x$ 到 $y$ ，最大权值2-Path的权值。 感谢@litble 提供翻译

题目描述

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) $ .

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #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

说明

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