[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 $𝑛$ vertices. The edge ${𝑢 𝑗, 𝑣 𝑗}$ has weight $𝑤 𝑗$ . Also each vertex $𝑖$ has its own value $𝑎 𝑖$ assigned to it.

Let’s call a path starting in vertex $𝑢$ and ending in vertex $𝑣$ , 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 $𝑝$ profit $P r (𝑝) = \sum 𝑣 \in d i s t i n c t v e r t i c e s i n 𝑝 𝑎 𝑣 - \sum 𝑒 \in d i s t i n c t e d g e s i n 𝑝 𝑘 𝑒 \cdot 𝑤 𝑒$ , where $𝑘 𝑒$ is the number of times edge $𝑒$ appears in $𝑝$ . That is, vertices are counted once, but edges are counted the number of times they appear in $𝑝$ .

You are about to answer $𝑚$ queries. Each query is a pair of vertices $(𝑞 𝑢, 𝑞 𝑣)$ . For each query find 2-path $𝑝$ from $𝑞 𝑢$ to $𝑞 𝑣$ with maximal profit $P r (𝑝)$ .

Input

The first line contains two integers $𝑛$ and $𝑞$ ( $2 \leq 𝑛 \leq 3 \cdot 105$ , $1 \leq 𝑞 \leq 4 \cdot 105$ ) — the number of vertices in the tree and the number of queries.

The second line contains $𝑛$ space-separated integers $𝑎 1, 𝑎 2, \dots, 𝑎 𝑛$ $(1 \leq 𝑎 𝑖 \leq 109)$ — the values of the vertices.

Next $𝑛 - 1$ lines contain descriptions of edges: each line contains three space separated integers $𝑢 𝑖$ , $𝑣 𝑖$ and $𝑤 𝑖$ ( $1 \leq 𝑢 𝑖, 𝑣 𝑖 \leq 𝑛$ , $𝑢 𝑖 \neq 𝑣 𝑖$ , $1 \leq 𝑤 𝑖 \leq 109$ ) — there is edge ${𝑢 𝑖, 𝑣 𝑖}$ with weight $𝑤 𝑖$ in the tree.

Next $𝑞$ lines contain queries (one per line). Each query contains two integers $𝑞 𝑢 𝑖$ and $𝑞 𝑣 𝑖$ $(1 \leq 𝑞 𝑢 𝑖, 𝑞 𝑣 𝑖 \leq 𝑛)$ — endpoints of the 2-path you need to find.

Output

For each query print one integer per line — maximal profit $P r (𝑝)$ of the some 2-path $𝑝$ 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$ . $P r (𝑝) = (𝑎 1 + 𝑎 2 + 𝑎 3 + 𝑎 4 + 𝑎 5) - (2 \cdot 𝑤 (1, 2) + 2 \cdot 𝑤 (2, 3) + 2 \cdot 𝑤 (2, 4) + 2 \cdot 𝑤 (4, 5)) = 21 - 2 \cdot 12 = 9$ .

$(4, 4)$ : $4 \to 2 \to 1 \to 2 \to 3 \to 2 \to 4$ . $P r (𝑝) = (𝑎 1 + 𝑎 2 + 𝑎 3 + 𝑎 4) - 2 \cdot (𝑤 (1, 2) + 𝑤 (2, 3) + 𝑤 (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
}