Double Tree

You are given two trees, both with $N$ vertices, numbered from 1 to $N$.

At the beginning, the weights of edges of both trees and the values of vertices of the first tree are given.

There are $Q$ operations. In each operation, the value of a vertice of the first tree will be modified. Please output $max_{1 \leq u < v \leq n}\left\{T_1.dis(u, v) + T_2.dis(u, v) + val(u) + val(v)\right\}$ after every operation.

Note that the symbol $T_{id}.dis(u,v)$ denotes the distance between vertice $u$ and vertice $v$ in the tree $id$.

Note that the distance between two vertices in some tree is defined as the sum of the weights in the simple path between the two vertices.

Note that the symbol $val(u)$ denotes the value of the vertice $u$ in the first tree.

There are multiple test cases.

Each case starts with a line containing two positive integers $N, Q(2 \leq N \leq 10^5, 1 \leq Q \leq 10^5)$.

The second line contains $N$ integers $a_1, a_2, ..., a_N(1 \leq a_i \leq 10^9)$ denoting the values of vertices of the first tree.

Then follow $N - 1$ lines. Each line contains three integers $u, v, w(1 \leq u, v \leq n, 1 \leq w \leq 10^9)$ describing the first tree. Namely, $u, v, w$ means that there is an edge weighted $w$ between vertice $u$ and vertice $v$.

Then follow $N - 1$ lines. Each line contains three integers $u, v, w(1 \leq u, v \leq n, 1 \leq w \leq 10^9)$ describing the second tree.

Then follow $Q$ lines. Each line contains two integers $u, w(1 \leq u \leq n, 1 \leq w \leq 10^9)$, denoting the value of vertice $u$ of the first tree will be modified to $w$.

It is guaranteed that the sum of $N$s and the sum of $Q$s in all test cases are both no larger than $2 \times 10^5$.

There is only one test case which contains $N$ and $Q$ that are both larger than $2 \times 10^4$.

It is guaranteed that $N$ and $Q$ in every other test case are all no larger than $2 \times 10^4$.

For each test case, output $Q$ lines. Each line contains an integer denoting the answer.

5 3
1 2 3 4 5
1 2 1
1 3 2
1 4 3
1 5 4
1 2 1
1 3 2
1 4 3
1 5 4
1 100
1 1
2 100

113
23
115

2019 Multi-University Training Contest 2