[CodeForces1000]G. Two-Paths

2018-06-28

lolifamily

作为压轴题，题目描述很长、很难理解。

还没写好 QwQ

G. Two-Paths

time limit per test: 3.5 secondsmemory limit per test: 256 megabytesinput: standard inputoutput: standard output

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 $Pr (p) = \sum_{v \in distinct vertices in p} a_{v} - \sum_{e \in 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 $(q u, q v)$ . For each query find 2-path $p$ from $q u$ to $q v$ with maximal profit $Pr (p)$ .

Input

The first line contains two integers $n$ and $q$ ( $2 \leq n \leq 3 \cdot 10^{5}$ , $1 \leq q \leq 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 \leq a_{i} \leq 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 \leq u_{i}, v_{i} \leq n$ , $u_{i} \neq v_{i}$ , $1 \leq w_{i} \leq 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 $q u_{i}$ and $q v_{i}$ $(1 \leq q u_{i}, q v_{i} \leq n)$ — endpoints of the 2-path you need to find.

Output

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

Example

input

1
7 6
2
6 5 5 3 2 1 2
3
1 2 2
4
2 3 2
5
2 4 1
6
4 5 1
7
6 4 2
8
7 3 25
9
1 1
10
4 4
11
5 6
12
6 4
13
3 4
14
3 7

output

Note

Explanation of queries:

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

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

$(5, 6)$ : $5 \to 4 \to 2 \to 3 \to 2 \to 1 \to 2 \to 4 \to 6$ .

$(6, 4)$ : $6 \to 4 \to 2 \to 1 \to 2 \to 3 \to 2 \to 4$ .

$(3, 4)$ : $3 \to 2 \to 1 \to 2 \to 4$ .

$(3, 7)$ : $3 \to 2 \to 1 \to 2 \to 4 \to 5 \to 4 \to 2 \to 3 \to 7$ .

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
int main(void)
7
{
8
  printf("还没写好 QwQ\n");
9
  return 0;
10
}