Two-Paths
Contest: Educational Codeforces Round 46 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, dp, trees

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

Input format:
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.

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

Constraints:
Time limit: 3.5 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
9
9
9
8
12
-14

Editorial:
Let's solve this task in several steps.
Step 1. Calculate $$$dp_i$$$ for each vertex.
Let $$$dp_i$$$ be maximal profit of some 2-path starting at $$$i$$$ and finishing at $$$i$$$. If vertex $$$i$$$ is a root of the tree, then $$$dp_i$$$ equivalent to $$$d'_i$$$, where $$$d'_i$$$ — maximal profit of 2-path $$$(i, i)$$$, when we can go only in subtree of $$$i$$$. The $$$d'_i$$$ can be calculated with next approach: $$$d'_v = a_v + \sum\limits_{to \in \text{Children}(v)}{\max(0, d'_{to} - 2 \cdot w(v, to))}$$$.
To calculate $$$dp_i$$$ we can use next technique. Let's manage next invariant: when processing vertex $$$v$$$ all its neighbours (even parent) will hold $$$d'_i$$$ as if $$$v$$$ its parent. Then $$$dp_v = a_v + \sum\limits_{to \in \text{Neighbours}(v)}{\max(0, d'_{to} - 2 \cdot w(v, to))}$$$. After that, we can proceed with each child $$$to$$$ of $$$v$$$, but before moving to it we must change value $$$d'_v$$$ since we must keep invariant true. To keep it true, it's enough to set $$$d'_v = dp_v - \max(0, d'_{to} - 2 \cdot w(v, to))$$$. Also let's memorize value $$$\max(0, d'_{to} - 2 \cdot w(v, to))$$$ as $$$dto(v, to)$$$.
Step 2. Processing queries.
Let simple path $$$(qu, qv)$$$ be $$$qu \rightarrow p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_k \rightarrow qv$$$. If $$$qu = qv$$$ then answer is $$$dp_{qu}$$$. Otherwise, each edge on this simple path must be used exactly once. But, while travelling from $$$qu$$$ to $$$qv$$$ using this simple path, at each vertex $$$v$$$ we can go somewhere and return to $$$v$$$ — the only condition is not use edges from simple path. And we can do it using precalculated values $$$dp_i$$$ and $$$dto(v, to)$$$. So, if we want to find max profit of 2-path $$$(v, v)$$$ with prohibited edges $$$(v, to_1)$$$, $$$(v, to_2)$$$, so we can use value $$$dp_v - dto(v, to_1) - dto(v, to_2)$$$.
Finally, to process queries, let's find $$$l = lca(qu, qv)$$$, divide it on two queries $$$(qu, l)$$$, $$$(qv, l)$$$. Now we can handle all queries offline, travelling on tree in dfs order. Let's manage some data structure on current path from current vertex to the root (this DS can be based on array of depths). Then, when we come to vertex $$$v$$$, just add value $$$dp_v - dto(v, \text{parent}(v))$$$ to DS in position $$$\text{depth}(v)$$$ (and erase it before exit). Each query $$$(v, l)$$$ becomes a query of sum to some subsegment in DS (don't forget carefully handle value in lca). And, before moving from $$$v$$$ to $$$to$$$, you need subtract $$$dto(v, to)$$$ from current value of $$$v$$$ (here you can at once subtract weight of edge $$$(v, to)$$$). Don't forget to return each change in DS, when it needed.
As we can see, DS is just a BIT with sum on segment and change in position.
Result complexity is $$$O((n + m) \log{n})$$$. Fast IO are welcome.