{"raw_statement":[{"iden":"statement","content":"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.\n\nLet'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).\n\nFor 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$.\n\nYou 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)$."},{"iden":"input","content":"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.\n\nThe 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.\n\nNext $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.\n\nNext $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."},{"iden":"output","content":"For each query print one integer per line — maximal profit $\\text{Pr}(p)$ of the some 2-path $p$ with the corresponding endpoints."},{"iden":"example","content":"Input\n\n7 6\n6 5 5 3 2 1 2\n1 2 2\n2 3 2\n2 4 1\n4 5 1\n6 4 2\n7 3 25\n1 1\n4 4\n5 6\n6 4\n3 4\n3 7\n\nOutput\n\n9\n9\n9\n8\n12\n-14"},{"iden":"note","content":"Explanation of queries:\n\n1.  $(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$.\n2.  $(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$.\n3.  $(5, 6)$: $5 \\rightarrow 4 \\rightarrow 2 \\rightarrow 3 \\rightarrow 2 \\rightarrow 1 \\rightarrow 2 \\rightarrow 4 \\rightarrow 6$.\n4.  $(6, 4)$: $6 \\rightarrow 4 \\rightarrow 2 \\rightarrow 1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 2 \\rightarrow 4$.\n5.  $(3, 4)$: $3 \\rightarrow 2 \\rightarrow 1 \\rightarrow 2 \\rightarrow 4$.\n6.  $(3, 7)$: $3 \\rightarrow 2 \\rightarrow 1 \\rightarrow 2 \\rightarrow 4 \\rightarrow 5 \\rightarrow 4 \\rightarrow 2 \\rightarrow 3 \\rightarrow 7$."}],"translated_statement":[{"iden":"note","content":"查询说明：\n\n$(1, 1)$：其中一个最优 2-path 如下：$1 \\to 2 \\to 4 \\to 5 \\to 4 \\to 2 \\to 3 \\to 2 \\to 1$。$\"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$。\n\n$(4, 4)$：$4 \\to 2 \\to 1 \\to 2 \\to 3 \\to 2 \\to 4$。$\"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$。\n\n$(5, 6)$：$5 \\to 4 \\to 2 \\to 3 \\to 2 \\to 1 \\to 2 \\to 4 \\to 6$。\n\n$(6, 4)$：$6 \\to 4 \\to 2 \\to 1 \\to 2 \\to 3 \\to 2 \\to 4$。\n\n$(3, 4)$：$3 \\to 2 \\to 1 \\to 2 \\to 4$。\n\n$(3, 7)$：$3 \\to 2 \\to 1 \\to 2 \\to 4 \\to 5 \\to 4 \\to 2 \\to 3 \\to 7$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges.  \nLet $ a_i \\in \\mathbb{R}^+ $ be the value assigned to vertex $ i \\in V $.  \nLet $ w_e \\in \\mathbb{R}^+ $ be the weight of edge $ e \\in E $.  \n\nA **2-path** $ p $ between vertices $ u $ and $ v $ is a walk (sequence of vertices and edges) from $ u $ to $ v $ such that each edge is traversed at most twice (in either direction).  \n\nDefine the **profit** of a 2-path $ p $ as:  \n$$\n\\text{Pr}(p) = \\sum_{v \\in \\text{distinct vertices in } p} a_v - \\sum_{e \\in E} k_e \\cdot w_e\n$$  \nwhere $ k_e \\in \\{0,1,2\\} $ is the number of times edge $ e $ is traversed in $ p $.\n\n**Constraints**  \n1. $ 2 \\le n \\le 3 \\cdot 10^5 $  \n2. $ 1 \\le q \\le 4 \\cdot 10^5 $  \n3. $ 1 \\le a_i \\le 10^9 $ for all $ i \\in V $  \n4. $ 1 \\le w_e \\le 10^9 $ for all $ e \\in E $  \n5. For each query $ (q_u, q_v) $, $ q_u, q_v \\in V $\n\n**Objective**  \nFor each query $ (u, v) $, compute:  \n$$\n\\max_{p: u \\leadsto v} \\left( \\sum_{x \\in \\text{vertices}(p)} a_x - \\sum_{e \\in E} k_e \\cdot w_e \\right)\n$$  \nwhere the maximum is taken over all 2-paths $ p $ from $ u $ to $ v $.","simple_statement":null,"has_page_source":false}